# Determine if a string is a permutation of another string efficiently [duplicate]

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?

• 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. – sel Jul 23 '17 at 20:21
• @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. – Filip Haglund Jul 23 '17 at 20:38
• 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? – 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.
• @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. – ryan Jul 23 '17 at 21:24