6. Valid Anagram

🔗 LeetCode Problem: 242. Valid Anagram
📊 Difficulty: Easy
🏷️ Topics: Hash Table, String, Sorting

Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Explanation: Both have same letters: a(3), n(1), g(1), r(1), m(1)

Example 2:

Input: s = "rat", t = "car"
Output: false
Explanation: Different letters

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

---

🎨 Visual Understanding

The Problem Visualized

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

String s: a n a g r a m
Count:    a(3), n(1), g(1), r(1), m(1)

String t: n a g a r a m
Count:    a(3), n(1), g(1), r(1), m(1)

Comparison: Same counts for all letters ✓
Result: true

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

String s: r a t
Count:    r(1), a(1), t(1)

String t: c a r
Count:    c(1), a(1), r(1)

Comparison: 
  - s has 't', t doesn't ✗
  - t has 'c', s doesn't ✗
Result: false

What Makes an Anagram?

Valid Anagram Requirements:
1. Same length
2. Same characters
3. Same frequency of each character

Examples:
"listen" → "silent" ✓ (rearrange letters)
"hello" → "world"   ✗ (different letters)
"aab" → "aba"       ✓ (same letters, same count)
"aab" → "aaa"       ✗ (different frequency)

Different Approaches Comparison

Approach 1: Sorting
"anagram" → sort → "aaagmnr"
"nagaram" → sort → "aaagmnr"
Compare: "aaagmnr" == "aaagmnr" ✓

Time: O(n log n)
Space: O(n) for sorted strings

Approach 2: Frequency Array
Count s: [3,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,0,0,0,0]
         a b c d e f g h i j k l m n o p q r s t u v w x y z
Count t: [3,0,0,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,0,0,0,0,0,0]
Compare arrays: Equal ✓

Time: O(n)
Space: O(1) - fixed 26 slots

Approach 3: HashMap
Count s: {a:3, n:1, g:1, r:1, m:1}
Count t: {a:3, n:1, g:1, r:1, m:1}
Compare maps: Equal ✓

Time: O(n)
Space: O(1) - at most 26 keys

---

🎯 Approach 1: Sorting

The Most Natural Thinking 💭

Core Logic:

If two strings are anagrams:
→ They contain the same letters
→ Sorting both will produce identical results

Steps:
1. Check if lengths are equal (quick filter)
2. Sort both strings
3. Compare sorted strings

Why This Works: - Sorting arranges letters in same order - If anagrams, sorted versions are identical - Simple and intuitive approach

Trade-off: - Sorting costs O(n log n) - Not optimal but easy to implement

Implementation

public boolean isAnagram(String s, String t) {
    // Quick check: different lengths can't be anagrams
    if (s.length() != t.length()) {
        return false;
    }

    // Convert to char arrays and sort
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();

    Arrays.sort(sChars);
    Arrays.sort(tChars);

    // Compare sorted arrays
    return Arrays.equals(sChars, tChars);
}

Step-by-Step Execution: s = "anagram", t = "nagaram"

Initial Check:
├─ s.length() = 7
├─ t.length() = 7
└─ Lengths equal ✓ Continue

Convert to arrays:
├─ sChars = ['a','n','a','g','r','a','m']
└─ tChars = ['n','a','g','a','r','a','m']

After sorting:
├─ sChars = ['a','a','a','g','m','n','r']
└─ tChars = ['a','a','a','g','m','n','r']

Compare:
├─ Position 0: 'a' == 'a' ✓
├─ Position 1: 'a' == 'a' ✓
├─ Position 2: 'a' == 'a' ✓
├─ Position 3: 'g' == 'g' ✓
├─ Position 4: 'm' == 'm' ✓
├─ Position 5: 'n' == 'n' ✓
└─ Position 6: 'r' == 'r' ✓

Result: true

⏰ Time: O(n log n) - sorting dominates
💾 Space: O(n) - char arrays

---

🎯 Approach 2: Frequency Array (Optimal for lowercase only)

Thought Process 💭

Core Logic:

Key Insight: Only 26 possible characters (a-z)

Strategy:
1. Count frequency of each character in s
2. Subtract frequencies while processing t
3. If all counts remain 0 → anagram!

Why This Works: - Each character maps to array index (a=0, b=1, ... z=25) - Increment for s, decrement for t - If anagram, all counts return to 0

Why This is Better: - O(n) single pass through both strings - O(1) space - fixed 26 slots regardless of input size - No sorting overhead

Implementation

public boolean isAnagram(String s, String t) {
    // Quick check: different lengths can't be anagrams
    if (s.length() != t.length()) {
        return false;
    }

    // Frequency array for 26 lowercase letters
    int[] count = new int[26];

    // Count characters in both strings
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;  // Increment for s
        count[t.charAt(i) - 'a']--;  // Decrement for t
    }

    // Check if all counts are zero
    for (int c : count) {
        if (c != 0) {
            return false;  // Frequency mismatch
        }
    }

    return true;
}

Step-by-Step Execution: s = "anagram", t = "nagaram"

Initial: count = [0,0,0,...,0] (26 zeros)

Processing both strings simultaneously:
═══════════════════════════════════════════════════════════════════

i=0: s[0]='a', t[0]='n'
├─ s: 'a'-'a'=0 → count[0]++ → count[0]=1
├─ t: 'n'-'a'=13 → count[13]-- → count[13]=-1
└─ count = [1,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,...]

i=1: s[1]='n', t[1]='a'
├─ s: 'n'-'a'=13 → count[13]++ → count[13]=0
├─ t: 'a'-'a'=0 → count[0]-- → count[0]=0
└─ count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]

i=2: s[2]='a', t[2]='g'
├─ s: 'a'-'a'=0 → count[0]++ → count[0]=1
├─ t: 'g'-'a'=6 → count[6]-- → count[6]=-1
└─ count = [1,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,...]

i=3: s[3]='g', t[3]='a'
├─ s: 'g'-'a'=6 → count[6]++ → count[6]=0
├─ t: 'a'-'a'=0 → count[0]-- → count[0]=0
└─ count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]

i=4: s[4]='r', t[4]='r'
├─ s: 'r'-'a'=17 → count[17]++ → count[17]=1
├─ t: 'r'-'a'=17 → count[17]-- → count[17]=0
└─ count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]

i=5: s[5]='a', t[5]='a'
├─ s: 'a'-'a'=0 → count[0]++ → count[0]=1
├─ t: 'a'-'a'=0 → count[0]-- → count[0]=0
└─ count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]

i=6: s[6]='m', t[6]='m'
├─ s: 'm'-'a'=12 → count[12]++ → count[12]=1
├─ t: 'm'-'a'=12 → count[12]-- → count[12]=0
└─ count = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]

Final count array: all zeros! ✓
Result: true

Another Example: s = "rat", t = "car"

Initial: count = [0,0,0,...,0]

i=0: s='r', t='c'
  count[17]++ → count[17]=1
  count[2]-- → count[2]=-1

i=1: s='a', t='a'
  count[0]++ → count[0]=1
  count[0]-- → count[0]=0

i=2: s='t', t='r'
  count[19]++ → count[19]=1
  count[17]-- → count[17]=0

Final count: [0,0,-1,0,...,0,1,0] (has non-zero values)
Result: false

⏰ Time: O(n) - single pass
💾 Space: O(1) - fixed 26 slots

---

✅ Approach 3: HashMap (Universal Solution)

The Breakthrough Insight 💡

Core Logic:

Why HashMap?
- Works for ANY character set (not just a-z)
- Unicode, special characters, etc.
- More flexible than fixed array

Strategy:
1. Count frequency of each char in s
2. Decrease count for each char in t
3. If any count becomes negative → not anagram
4. If any count remains positive → not anagram

When to Use: - Unicode characters allowed - Mixed case (uppercase + lowercase) - Special characters included - More general solution

Implementation

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    HashMap<Character, Integer> count = new HashMap<>();

    // Count characters in s
    for (char c : s.toCharArray()) {
        count.put(c, count.getOrDefault(c, 0) + 1);
    }

    // Decrease counts for t
    for (char c : t.toCharArray()) {
        if (!count.containsKey(c)) {
            return false;  // Character not in s
        }
        count.put(c, count.get(c) - 1);
        if (count.get(c) < 0) {
            return false;  // Too many of this character in t
        }
    }

    return true;
}

Step-by-Step Execution: s = "anagram", t = "nagaram"

Phase 1: Count characters in s
═══════════════════════════════════════════════════════════════════
Process 'a': count = {a:1}
Process 'n': count = {a:1, n:1}
Process 'a': count = {a:2, n:1}
Process 'g': count = {a:2, n:1, g:1}
Process 'r': count = {a:2, n:1, g:1, r:1}
Process 'a': count = {a:3, n:1, g:1, r:1}
Process 'm': count = {a:3, n:1, g:1, r:1, m:1}

Phase 2: Decrease counts for t
═══════════════════════════════════════════════════════════════════
Process 'n': count = {a:3, n:0, g:1, r:1, m:1}
Process 'a': count = {a:2, n:0, g:1, r:1, m:1}
Process 'g': count = {a:2, n:0, g:0, r:1, m:1}
Process 'a': count = {a:1, n:0, g:0, r:1, m:1}
Process 'r': count = {a:1, n:0, g:0, r:0, m:1}
Process 'a': count = {a:0, n:0, g:0, r:0, m:1}
Process 'm': count = {a:0, n:0, g:0, r:0, m:0}

All counts reached 0 ✓
Result: true

⏰ Time: O(n)
💾 Space: O(1) - at most 26 keys for lowercase

---

🔍 Edge Cases

Case 1: Same string
Input: s = "abc", t = "abc"
Output: true
Strategy: Identical strings are anagrams

Case 2: Empty strings
Input: s = "", t = ""
Output: true
Strategy: Empty is anagram of empty

Case 3: Different lengths
Input: s = "a", t = "ab"
Output: false
Strategy: Early exit on length check

Case 4: One character difference
Input: s = "ab", t = "ac"
Output: false

Case 5: Same letters, different frequency
Input: s = "aab", t = "aaab"
Output: false
Reason: Different counts

Case 6: All same character
Input: s = "aaaa", t = "aaaa"
Output: true

Case 7: Reversed string
Input: s = "abc", t = "cba"
Output: true
Strategy: Order doesn't matter

Case 8: Unicode characters (if allowed)
Input: s = "你好", t = "好你"
Output: true
Strategy: HashMap handles Unicode

---

Common Mistakes

Mistake 1: Not checking length first
❌ Wrong: Process both strings without length check
✓ Right: Early exit if lengths differ

Mistake 2: Case sensitivity issues
❌ Wrong: Treat 'A' and 'a' as different
✓ Right: Convert to lowercase first (if needed)

Mistake 3: Off-by-one in array indexing
❌ Wrong: count[s.charAt(i) - 'A']  // Wrong for lowercase
✓ Right: count[s.charAt(i) - 'a']  // Correct for lowercase

Mistake 4: Not handling negative counts
❌ Wrong: Only check if count[i] == 0 at end
✓ Right: Also check for negative during processing

Mistake 5: Creating two separate count arrays
❌ Wrong: Use two arrays and compare
✓ Right: Use one array, increment/decrement

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Sorting
  Time: O(n log n)
  Space: O(n)
  Use: Simple, easy to code

Approach 2: Frequency Array (BEST for lowercase)
  Time: O(n)
  Space: O(1) - fixed 26
  Use: Optimal for a-z only

Approach 3: HashMap
  Time: O(n)
  Space: O(1) - at most 26
  Use: Universal (Unicode, mixed case)

🔑 The Core Insight

Anagram = Same letters with same frequency

Three ways to verify:
1. Sort and compare (simple but slower)
2. Count frequency and match (optimal)
3. Count with increment/decrement (space-efficient)

Best approach depends on constraints:
→ Lowercase only? Frequency array
→ Unicode/mixed? HashMap
→ Quick code? Sorting

🎯 Pattern Recognition

Problem Type: Character Frequency Comparison
Core Pattern: Count and match

When to Apply:
✓ Anagram detection
✓ String permutation checking
✓ Character frequency comparison
✓ "Same letters, different order"

Key Techniques:
→ Frequency counting (array or map)
→ Increment/decrement pattern
→ Early termination on length mismatch

Related Problems:
- Group Anagrams (LC 49)
- Find All Anagrams in String (LC 438)
- Permutation in String (LC 567)
- Valid Palindrome (LC 125)

🧠 Interview Strategy

Step 1: "Need to check if strings have same letters with same frequency"
Step 2: "Sorting works but is O(n log n)"
Step 3: "Frequency counting is O(n) - better"
Step 4: "For lowercase only, use 26-size array"
Step 5: "For general case, use HashMap"

---

📝 Quick Revision Notes

🎯 Core Concept:

Anagram = same characters with same frequency. Count characters in one string, verify counts match in other string.

⚡ Quick Implementation:

public boolean isAnagram(String s, String t) {
    if(s.length() != t.length()) {
        return false;
    }

    // Approach 1 - using freq array (works only for lower case letters)
    // int[] count = new int[26];
    // for(int i = 0; i < s.length(); i++) {
    //     count[s.charAt(i) - 'a']++; // let s increase the count
    //     count[t.charAt(i) - 'a']--; // let t decrease the count            
    // }

    // for(int i = 0; i < count.length; i++) {
    //     if(count[i] != 0) {
    //         return false; // if they are not anagrams, some char mismatch lead to non-zero
    //     }
    // }

    // return true;

    // Approach 2 - using map (works for all chars)
    HashMap<Character, Integer> map = new HashMap<>();
    for(int i = 0; i < s.length(); i++) {
        map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) - 1);
    }

    for(int value : map.values()) {
        if(value != 0) {
            return false;
        }
    }

    return true;
}

🔑 Key Insights:

• Early exit on length mismatch
• Frequency array for fixed character set (O(1) space)
• HashMap for general case (Unicode, mixed case)
• Increment/decrement pattern saves space
• Single pass through both strings simultaneously

🎪 Memory Aid:

"Same letters, same frequency = Anagram!"
Think: "Count up for s, count down for t, all should be zero"

---

Related Patterns

• Group Anagrams (LC 49)
• Find All Anagrams in String (LC 438)
• Permutation in String (LC 567)

---

Happy practicing! 🎯