Faced this question in an interview, which basically stated

Find if the given two strings are anagrams of each other in O(N) time without any extra space

I tried the usual solutions:

1. Using a character frequency count (O(N) time, O(26) space)
2. Sorting both strings and comparing (O(NlogN) time, constant space)

But the interviewer wanted a "better" approach. At the extreme end of the interview, he hinted at "XOR" for the question. Not sure how that works, since "aa" XOR "bb" should also be zero without being anagrams.

Long story short, are the given constraints possible? If so, what would be the algorithm?

CodePudding user response：

given word_a and word_b in the same length, I would try the following:

1. Define a variable counter and initialize the value to 0.

2. For each letter ii in the alphabet do the following:

   2.1. for jj in length(word_a):

   2.1.1. if word_a[jj] == ii increase counter by 1: counter = 1

   2.1.2. if word_b[jj] == ii decrease the counter by 1: counter -= 1

   2.2. if after passing all the characters in the words, counter is different than 0, you have a different number of ii characters in each word and in particular they are not anagrams, break out of the loop and return False

3. Return True

Explenation

In case the words are anagrams, you have the same number of each of the characters, therefore the use of the histogram makes sense, but histograms require space. Using this method, you run over the n characters of the words exactly 26 times in the case of the English alphabet or any other constant c representing the number of letters in the alphabet. Therefor, the runtime of the process is O(c*n) = O(n) since c is constant and you do not use any other space besides the one variable

CodePudding user response：

I haven't proven to myself that this is infallible yet, but it's a possible solution.

Go through both strings and calculate 3 values: the sum, the accumulated xor, and the count. If all 3 are equal then the strings should be anagrams.