Valid Anagram — The Frequency-Map Pattern Every FAANG Asks

Problem Statement#

Given two strings s and t, return true if t is an anagram of s. An anagram uses each letter of s exactly once.

Constraints:

• 1 <= s.length, t.length <= 5 * 10^4
• s and t consist of lowercase English letters.

Input:  s = "anagram", t = "nagaram"
Output: true

Input:  s = "rat", t = "car"
Output: false

Why This Problem Matters#

LeetCode 242 Valid Anagram is the standard frequency-map warm-up at Amazon, Microsoft, Google, and Meta. The interview signal is whether you reach for a 26-element frequency array (the optimal hashmap interview structure for lowercase ASCII) instead of sorting both strings.

The frequency-count pattern reappears in Ransom Note, Group Anagrams, Find All Anagrams in a String, Permutation in String, and Minimum Window Substring. Master Valid Anagram and the entire family becomes a one-line variant. Recruiters specifically watch for the optimization conversation: O(1) space using a fixed array versus O(k) space using a HashMap when characters extend beyond ASCII.

In production systems, the same idea backs spam detection (matching shuffled token bags), bag-of-words classification, and DNA k-mer comparison.

The Core Insight#

Two strings are anagrams if and only if their character multisets are equal. The optimal procedure: increment a counter for every character in s, decrement for every character in t. If lengths differ, return false instantly. If all 26 counters are zero at the end, return true. A negative count proves a mismatch.

The fixed array of size 26 is the textbook hash table FAANG trick: deterministic O(1) lookup with zero collision overhead and minimal constant factors.

Visual Dry Run#

Input s = "anagram", t = "nagaram":

All counters return to 0 — answer true.

Solution (Optimal)#

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count = [0] * 26
        for cs, ct in zip(s, t):
            count[ord(cs) - 97] += 1
            count[ord(ct) - 97] -= 1
        return all(c == 0 for c in count)

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    const count = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i) - 97]++;
        count[t.charCodeAt(i) - 97]--;
    }
    return count.every(c => c === 0);
};

Time: O(n) because we sweep both strings once. Space: O(1) because the 26-element counter is independent of input length.

Common Mistakes#

• Skipping the length check. Different-length strings can never be anagrams; the early exit avoids wasted work.
• Using a HashSet instead of a frequency map. Sets cannot tell aab apart from abb.
• Indexing with raw ord(c) without subtracting ord('a'). Returns 97 instead of 0 and overflows.
• Sorting both strings as the only solution. Works but O(n log n); interviewers want the linear answer.
• Hard-coding 26 when the follow-up extends to Unicode. Switch to a dict or Map for arbitrary alphabets.

Interview Tips#

• Mention collections.Counter in Python, but show the manual array first to prove fluency.
• Discuss the Unicode follow-up proactively; it is the most common extension at Google.
• Stress the O(1) space claim: 26 is constant relative to input length, even though the array exists.
• For JavaScript, prefer charCodeAt(i) - 97 over Map; arrays are faster for fixed alphabets.

Follow-up Questions#

• What if s and t contain Unicode? (Hint: replace the array with a HashMap; algorithm is identical.)
• Can you use Counter equality? (Hint: Counter(s) == Counter(t) works but allocates more memory.)
• How would you stream comparisons of many (s, t) pairs efficiently? (Hint: cache frequency tuples per string.)
• Generalize to Group Anagrams (LC 49). (Hint: use the frequency tuple as a HashMap key.)
• Why is sorting suboptimal here? (Hint: O(n log n) versus the linear hash solution.)

Key Takeaways#

• LeetCode 242 Valid Anagram trains the frequency-array hashmap pattern.
• A 26-element array gives O(1) space when input is lowercase ASCII.
• Always check len(s) == len(t) before counting.
• One pass increments for s and decrements for t; final counters must be all zero.
• For Unicode, swap the array for a HashMap; the algorithm is unchanged.
• Sorting both strings works but takes O(n log n); the hash solution is O(n).
• The frequency-count pattern is reused in Group Anagrams, Find All Anagrams, and Permutation in String.