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?