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

This question already has an answer here:

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?

## marked as duplicate by Filip Haglund, Community♦Jul 23 '17 at 21:13

• 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