Check if two strings are permutation of each other

Question

  private String sort(String word) {
    char[] content = word.toCharArray();
    Arrays.sort(content);
    return new String(content);
  }

  private boolean isPermutation(String s1, String s2) {
    s2 = s2.toLowerCase();
    if (s1.length() != s2.length()) {
      return false;
    }
    if (s1.equals(s2)) {
      return true;
    }
    return sort(s1).equals(sort(s2));
  }

Could the above solution can be optimized(in space and time)?
I think the worst case running time would be: \$O(nlog)\$

Answer 1

For short strings, this algorithm and the implementation is good.

If your strings are longer than a few 100 characters and if they only contain ASCII characters, it may be more efficient to count how many times each character appears and then compare if all these counts are equal. This algorithm has complexity \$O(n)\$, but the (invisible) constant factor is larger.

If your strings contain arbitrary Unicode code points, using a simple array for the counts becomes impractical, since that array needs to have 0x11_0000 entries. Looping over these entries and comparing them is \$O(1)\$, but nevertheless it is slow.

Therefore, for practical purposes and the general case, your code looks perfect. There might be some improvements if you know more about the string's contents, but these are on the implementation level, not on the algorithm complexity level.

Answer 2

Here's what we have so far:

• Sorting using a general sort algorithm will be O(NlogN) on average where N is the number of characters.

• Sorting using a counting sort will be O(N), but will require O(A) space, where A is the "size" of the alphabet, and O(A) startup cost.

There is an approach which will you O(N) time in the best and average cases¹, in the worst case O(NlogN), and no memory usage / startup.

All you need is to design a hashing algorithm that is sensitive to the characters in the string, but insensitive to their position. A really simple one would be so sum or take the product of the character codes, using int or long arithmetic. Then the algorithm is this:

boolean isPermuntation(String a, String b) {
   if (hash(a) != hash(b)) {
      return false;
   } else {
      return sorted(chars(a)).equals(sorted(chars(b));
   }
}

The worst cases occur what a and b are permutations, or when they are not but the hashes turn out to be the same.

---

^{1 - On average ... for strings chosen at random from the set of all strings less than a certain length.}