Algorithms for Detecting Anagrams
This is one of my favorite warmup questions for technical interviews. It’s a very simple problem with many solutions and also gives away an idea of the candidates analytical skills.
Problem Statement
An anagram of a string is another string that contains the same characters, only the order of characters can be different.
Write a program to check whether two given strings are anagrams.
Leetcode : https://leetcode.com/problems/valid-anagram
NOTE : Assume english language alphabets in lowercase.
Examples:
- “abcd” & “dabc” — True
- “abccc” & “abc” — False
- “xyz” & “abc” — False
- “silent” & “listen” — True
From an interviewer perspective, any algorithm better than O(NlogN) is worth to start the discussion.
Base Cases:
It’s very easy to conclude that if length of two strings are not equal they are not anagrams since there is always a missing letter among them.
Solution 1 : Using Sorting
This is what most of us tend to come up with first. Sorting two anagrams will make them equal. See the python code below:
Now this works well, but it’s not the best solution in terms of time complexity.
Solution 2 : Using Letter Frequency
If we construct a letter frequency dictionary for both strings, they should be equal for anagrams. This is the best solution in terms of performance at the expense of an extra space, but it’s faster than sorting as it’s a linear time solution.
Solution 3 : Using Prime Factorization
This is probably the best solution for relatively smaller sized strings. The whole idea is around the concept of prime factorization in number theory. If we assign each letter a unique prime number, then the product of prime numbers of letters in first and second strings should be equal for anagrams.
Now the above solution will go into overflow for large strings and in python this will have serious performance issues when the products goes huge.
Leetcode Questions for Practice
- https://leetcode.com/problems/valid-anagram
- https://leetcode.com/problems/group-anagrams
- https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram
- https://leetcode.com/problems/find-all-anagrams-in-a-string
- https://leetcode.com/problems/determine-if-two-strings-are-close
NOTE : Anagram based question was also part of my Amazon SDE interview. Checkout out my other stories:
