Are 2 Strings Anagrams or Not?

Problem:
Given 2 strings, determine if they are anagrams. Anagram means the 2 strings contain exactly the same characters and number of appearances. In other words, we can do a permutation to get the other string from one string.

Solution 1:
Sort the 2 strings first, then if they are anagrams, the sorted strings must be identical. Otherwise, they are not.

In C++, we may use the library function sort in the header < algorithm >. This function is comparison based and the average time complexity is \(O(n\log n)\).


Solution 2:
Since the character values are always in a fixed range, and in this case, counting sort is good approach. In this way, we may obtain \(O(n)\) time complexity and \(O(n)\) space complexity.


Solution 3:
Similar to the idea of counting sort, we don't actually sort the strings. All we need is the counts of characters appearing in the strings. If the counts for each character are equal, then the 2 strings are anagram. This solution also exhibit \(O(n)\) time complexity, but \(O(1)\) space complexity.


Solution 4:
Even more, we can just count the characters for one string, and make judgement while scanning the other. This approach also has \(O(n)\) time complexity and \(O(1)\) space complexity.
There is a bug in Solution 4. What if s1 is longer and contains all characters in s2? For example, s1="abcd", s2="ab".

Two possible solutions for this:

1. Add a length check at the beginning. Two strings must be of the same length to be anagram.
2. Add another round of check on the count array after scanning the second string. All entries should be 0.