Valid Anagram

How it works

Since the problem guarantees lowercase English letters, we can use a fixed-size array of length 26 to count character frequencies instead of a hash map. As we iterate through both strings simultaneously, we increment the count for each character in s and decrement the count for each character in t. If the strings are anagrams, every increment will be matched by a corresponding decrement, and all values in the array will end at 0. This approach is efficient because it avoids hashing and uses constant space.

Steps

1. If the lengths of the strings differ, return false immediately.
2. Create a frequency array count of size 26 initialized to 0.
3. Iterate through both strings:
   • Increment the count at the index corresponding to s[i].
   • Decrement the count at the index corresponding to t[i].
4. After processing both strings, scan through the count array:
   • If any value is not 0, return false because the frequencies differ.
5. If all values are 0, return true since the strings are anagrams.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(1) since we have at most 26 different characters.

Where n is the length of string s and m is the length of string t.

Things to watch for

Forgetting to Check Length First

If two strings have different lengths, they cannot be anagrams. Skipping this early check means wasting time processing strings that could never match. Always compare lengths first and return false immediately if they differ.

Case Sensitivity Issues

When the problem specifies lowercase letters only (as in this problem), case sensitivity is not an issue. However, if the problem allows mixed case, forgetting to normalize to the same case (e.g., converting both strings to lowercase) will cause incorrect results where "Listen" and "Silent" would wrongly be considered non-anagrams.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        for val in count:
            if val != 0:
                return False
        return True

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }

        vector<int> count(26, 0);
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }

        for (int val : count) {
            if (val != 0) {
                return false;
            }
        }
        return true;
    }
};