Valid Anagram - String Frequency Guide

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

Two strings are anagrams when they contain the same characters with the same frequencies, just arranged in a different order.

Examples

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

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

Constraints

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

🎯 Real-World Analogy

Inventory Reconciliation

Imagine two warehouse bins. To confirm they hold identical inventory, you do not care about item order on shelves; you care about counts per item SKU.

If one bin has 4 blue widgets and the other has 3, they are not equivalent. Anagram checks work exactly the same way: character counts must match perfectly.

💡 Key Insights

If lengths differ, strings cannot be anagrams.
Character frequency map solves the problem in linear time.
Sorting also works, but usually costs extra O(N log N).
For fixed lowercase alphabet, space can be treated as O(1).

💻 Solution Approaches

Approach 1: Sort Both Strings

Time: O(N log N) | Space: O(N)

Sort s and t and compare. Simple, but more expensive than needed.

Approach 2: Frequency Counter (Recommended)

Time: O(N) | Space: O(1) for fixed alphabet

Count characters in s, subtract using t, and ensure all counts end at zero.

Python Implementation

          from collections import Counter


def is_anagram(s: str, t: str) -> bool:
    """
    Return True when s and t contain identical character frequencies.

    Time: O(N)
    Space: O(1) for lowercase English letters
    """
    if len(s) != len(t):
        return False

    counts = Counter()

    for ch in s:
        counts[ch] += 1

    for ch in t:
        counts[ch] -= 1
        if counts[ch] < 0:
            return False

    return True
        

JavaScript Implementation

          function isAnagram(s, t) {
  /**
   * Time: O(N)
   * Space: O(1) for lowercase English letters
   */
  if (s.length !== t.length) return false;

  const counts = new Array(26).fill(0);

  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i) - 97] += 1;
    counts[t.charCodeAt(i) - 97] -= 1;
  }

  for (const c of counts) {
    if (c !== 0) return false;
  }

  return true;
}
        

🔍 Step-by-Step Walkthrough

Trace s = "listen", t = "silent":

Initialize: counts = {}

            Count chars in s: l:1, i:1, s:1, t:1, e:1, n:1
          
            Subtract chars in t: s:0, i:0, l:0, e:0, n:0, t:0
          
All zero: valid anagram ✓

⚡ Complexity Analysis

Time Complexity: O(N)

One pass over s and one pass over t.
Each update/lookup in fixed-size array or hash map is O(1).

Space Complexity: O(1) / O(K)

Lowercase English letters imply fixed 26 buckets -> O(1).
General Unicode variant would be O(K), where K is unique chars.

🔧 Edge Cases

Different lengths immediately return false.
Same letters but different counts (e.g., "aacc" vs "ccac").
Single-character strings.
Repeated characters with large frequency.

🧪 Test Cases

Case 1
("anagram", "nagaram") -> true

Case 2
("rat", "car") -> false

Case 3
("aacc", "ccac") -> false

💼 Interview Tips

Lead with the length check optimization first.
Explain sort-vs-count tradeoff clearly.
Mention Unicode follow-up and how data structure choice changes.
Discuss why frequency arrays are faster than object maps for lowercase constraints.

🎓 Key Takeaways

Anagrams are frequency-equality problems, not ordering problems.
Length mismatch gives immediate fail-fast behavior.
Frequency counting is linear and interview-friendly.
Constraint-aware data structures (array vs map) are a key optimization story.

← Back to All Algorithms