Determine if a string is a permutation of another string efficiently 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 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.