Algorithms and Data Structures · Junior · Question 44 of 75
How do you check that two strings are anagrams in O(n)?
- 1Check that both strings have the same length
- 2Check that every character of the first string is in the second
- ✓Correct answer: Count the characters of both strings and compare the counts
Explanation
Count characters of the first string in a map, subtract the second string, and check that all counts are zero. Equal length isn't enough, and the "every character is present" check ignores how many times it appears ("aab" vs "abb"). Sorting both strings works too, but costs O(n log n).