How can I check if two strings are permutations of each other in O(n) time? (java)

Question

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.

How can this program be made more efficient?

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 < first.length(); i++){
         if (second.indexOf(first.charAt(i)) == -1){
            System.out.println("Not permutations");
            return false;
         } 
      }
      System.out.println("permutations");
      return true;
   }
}

Never mind making it more efficient, it's not correct. This will say that `AAAAT` is a permutation of `TTTTA`. — Andy Turner, Sep 30 '16 at 20:52
Count the number of each character for each string and compare they are the same. — Tony Lee, Sep 30 '16 at 20:53
Depends on the situation, but if you know it will only be characters in the ascii range, I would probably just create an `int[256]` and use bucket sort to see if they have all the same number of the same characters — jonhopkins, Sep 30 '16 at 20:54

score 8 · Answer 1 · answered Sep 30 '16 at 20:53

8

First, it can be done in O(nlogn) by sorting the two strings (after converting them to char[]), and then simple equality test will tell you if the original strings are permutations or not.

An O(n) solution average case can be achieved by creating a HashMap<Character, Integer>, where each key is a character in the string, and the value is the number of its occurances (This is called a Histogram). After you have it, again a simple equality check of the two maps will tell you if the original strings are permutations.

answered Sep 30 '16 at 20:53

amit

175,853
27
231
333

2

Instead of a HashMap you could use `int[65536]` for a constant memory usage. (or `int[128]` for ASCII) +1 for text it is more often called a frequency count. A "histogram" is more often used for the distribution of numbers. (characters are numbers I know but that's not how they are usually thought of) – Peter Lawrey Sep 30 '16 at 21:00

Mein Name · Accepted Answer · 2016-09-30T21:12:38.970

One way to archive O(n) is to count the frequency of every character.

I would use a HashMap with the characters as keys and the frequencys as values.

//create a HashMap containing the frequencys of every character of the String  (runtime O(n) )
public HashMap<Character, Integer> getFrequencys(String s){
    HashMap<Character, Integer> map = new HashMap<>();

    for(int i=0; i<s.length(); i++){
        //get character at position i
        char c = s.charAt(i);

        //get old frequency (edited: if the character is added for the 
        //first time, the old frequency is 0)
        int frequency;
        if(map.containsKey(c)){
            frequency = map.get(c);
        }else{
            frequency = 0;
        }
        //increment frequency by 1
        map.put(c, frequency+1 );
    }

    return map;
}

now you can create a HashMap for both Strings and compare if the frequency of every character is the same

//runtime O(3*n) = O(n)
public boolean compare(String s1, String s2){
    if(s1.length() != s2.length()){
        return false;
    }

    //runtime O(n)
    HashMap<Character, Integer> map1 = getFrequencys(s1);
    HashMap<Character, Integer> map2 = getFrequencys(s2);

    //Iterate over every character in map1 (every character contained in s1)  (runtime O(n) )
    for(Character c : map1.keySet()){
        //if the characters frequencys are different, the strings arent permutations
        if( map2.get(c) != map1.get(c)){
            return false;
        }
    }

    //since every character in s1 has the same frequency in s2,
    //and the number of characters is equal => s2 must be a permutation of s1

    return true;
}

edit: there was a nullpointer error in the (untested) code

Manan Bakshi · Answer 3 · 2017-10-24T07:04:47.263

Sorting Solution:

public void IsPermutation(String str1, String str2) {
  char[] sortedCharArray1 = Arrays.sort(str1.toCharArray());
  char[] sortedCharArray2 = Arrays.sort(str2.toCharArray());

  return Arrays.equals(sortedCharArray1, sortedCharArray2);
}

Time Complexity: O(n log n) Space Complexity: O(n)

Frequency count solution:

//Assuming that characters are only ASCII. The solutions can easily be modified for all characters

public void IsPermutation(String str1, String str2) {
    if (str1.length() != str2.length())
        return false;

    int freqCountStr1[] = new int[256];
    int freqCountStr2[] = new int[256];

    for (int i = 0; i < str1.length(); ++i) {
        int c1 = str1.charAt(i);
        int c2 = str2.charAt(i);
        ++freqCountStr1[c1];
        ++freqCountStr2[c2];
    }

    for (int i = 0; i < str1.length(); ++i) {
        if (freqCountStr1[i] != freqCountStr2[i]) {
            return false;
        }
    }

    return true;
  }
}

Time Complexity: O(n) Space Complexity: O(256)

How can I check if two strings are permutations of each other in O(n) time? (java)

3 Answers3