3

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?

Abhinav Mathur
  • 7,791
  • 3
  • 10
  • 24
  • They are anagrams if the character counts are the same, right? No need to sort. – Wyck Mar 22 '22 at 17:26
  • @Wyck: if, but not ony if. –  Mar 22 '22 at 17:28
  • @Wyck: Character frequency and sorting + string comparison are two alternative approaches. – M Oehm Mar 22 '22 at 17:28
  • For the 'without any extra space' constraint, does this allow modifying the input strings (if they are stored as character arrays)? – kcsquared Mar 22 '22 at 17:58
  • 1
    Does this answer your question? [How to check if two words are anagrams](https://stackoverflow.com/questions/15045640/how-to-check-if-two-words-are-anagrams) – Wyck Mar 22 '22 at 18:08
  • 5
    This looks like an interviewer being enamoured with a cool xor solution, even if it's wrong. A quick web search brings up [this](https://pragmaticdevs.wordpress.com/2015/12/27/finding-if-two-strings-are-anagrams-or-not-using-xor/) prettily typeset article and [this](https://www.javainterviewpoint.com/anagram-program-in-java/) article about six ways to test anagrams even walks through the code in minute detail. [This](https://stackoverflow.com/questions/50475317/resolving-equal-xor-values-for-different-strings-for-anagram-detection) SO answer has more on why xor is only a necessary condition. – M Oehm Mar 22 '22 at 18:11
  • 1
    There's also the non-XOR solution where you associate letters with the first 26 primes (a <-> 2, b <-> 3, ...) and take the product for each string. It's hard to see how this is any more space efficient, if the hashmap of frequencies solution wasn't good enough. – kcsquared Mar 22 '22 at 18:13
  • 1
    If it's given there's no duplicate letters in either of the words, xor works. – Paul Hankin Mar 22 '22 at 18:20
  • 2
    @PaulHankin I'm not sure that's true, at least for the naive XOR solution. For example, (7 XOR 3) = (5 XOR 1) = 4, and there are no duplicates. Also, if there are no duplicates, and since it appears all characters are lowercase letters, then the strings have length at most 26. – kcsquared Mar 22 '22 at 18:25
  • 1
    @MOehm "an interviewer being enamored with a cool xor solution, even if it's wrong." --> sad, but very likely true. Makes for a good interview quandry: How to handle an interviewer with an objectively wrong understanding? Likely a good (or dupe) question for another SE site. – chux - Reinstate Monica Mar 22 '22 at 21:24
  • I am reminded of a group of mathematicians who, after attending a lecture given by a famous mathematician who presented a proof of the validity of a long-standing conjecture, agree with each other that the proof was trivial. – Cary Swoveland Mar 23 '22 at 00:02
  • @kcsquared sorry, I wasn't clear what I thought the xor solution was, which was xor-ring 1< – Paul Hankin Mar 23 '22 at 06:04
  • @chux: To be fair, we don't know whether the interviewer's intention was to provoke that quandary: Nudge the candidate into providing an "even better" solution, which is what a customer might do, and then let them realize the mistake and see how they handle the situation. – M Oehm Mar 23 '22 at 06:14

2 Answers2

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

Freddy Mcloughlan
  • 4,129
  • 1
  • 13
  • 29
Tomer Geva
  • 1,764
  • 4
  • 16
  • This approach is correct, I had tried it as well. Forgot to mention it in the question, didn't sit well with the interviewer anyways – Abhinav Mathur Mar 23 '22 at 13:16
-1

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.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622