Given two strings of the same length, determine if they are permutations of each other.

I can come up with two solutions, one in O(n log n) time with O(1) extra space, and one in O(n) time with O(n) extra space, but I'm wondering if there are more efficient algorithms.

If we sort the strings in-place and compare them, we get O(n log n) time with O(1) extra space.

If we use a hashtable from character to count, we can keep track of how many of each character we have in the first string, and subtract accordingly when reading characters from the second string. That's O(n) time and O(n) extra space.

Can we do better?

  • $\begingroup$ You can build a histogram of the characters for each string an compare the histograms. If they are the same, then the strings are permutations of each other. It requires O(n) time (if string's length is n) and O(|alphabet|) space. $\endgroup$ – sel Jul 23 '17 at 20:21
  • $\begingroup$ @sel Isn't that the same as my second solution, except for me messing up and writing O(n) when I ment O(|alphabet|)? Right now, my second solution looks like a multiset rather than a set of counters. $\endgroup$ – Filip Haglund Jul 23 '17 at 20:38
  • 1
    $\begingroup$ What do you want to improve? Time? Assume you improved time down to $O(log(n))$. That means many elements in the array weren't even accessed at least once. Is it possible to decide without even access them once? $\endgroup$ – fade2black Jul 23 '17 at 20:50

You can establish a trivial lower bound of $\Omega(n)$, because you must at least observe all characters of each string (in worst case) to determine if they are permutations of each other. So $O(n)$ time complexity is the best you could do.

Perhaps you could improve the space complexity though. Raphael describes a unique approach here to achieve constant space and linear time using properties of prime numbers.

  • $\begingroup$ It's not quite O(n) since you'd need a bignum library for multiplying those numbers, but it's good enough. $\endgroup$ – Filip Haglund Jul 23 '17 at 21:20
  • $\begingroup$ @FilipHaglund, it would be $O(n)$ in a uniform cost RAM model as Raphael mentions, although that model of computation wouldn't be as useful as perhaps a logarithmic cost model in this context. $\endgroup$ – ryan Jul 23 '17 at 21:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.