title: How can I check if two strings are permutations of each other in O(n) time? (java)
body: <p>I wrote this class that can check if two given strings are permutations of each other. However, it is my understanding that this runs at O(n^2) time because the string.indexOf() runs at O(n) time.</p>
  
  <p>How can this program be made more efficient?</p>
  
  <pre><code>import java.util.*;
  
  public class IsPermutation{
     public void IsPermutation(){
        System.out.println("Checks if two strings are permutations of each other.");
        System.out.println("Call the check() method");
     }
  
     public boolean check(){
        Scanner console = new Scanner(System.in);
        System.out.print("Insert first string: ");
        String first = console.nextLine();
        System.out.print("Insert second string: ");
        String second = console.nextLine();
  
        if (first.length() != second.length()){
           System.out.println("Not permutations");
           return false;
        }
  
        for (int i = 0; i &lt; first.length(); i++){
           if (second.indexOf(first.charAt(i)) == -1){
              System.out.println("Not permutations");
              return false;
           } 
        }
        System.out.println("permutations");
        return true;
     }
  }
  </code></pre>