'Find if two strings are anagrams

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) (as a variation, iterating 26 times to calculate frequency of each character as well)
  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?

stringalgorithm


Solution 1:[1]

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

  1. Define a variable counter and initialise 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

Explanation

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

Solution 2:[2]

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.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Freddy Mcloughlan
Solution 2 Mark Ransom

Related Questions