02 valid anagram

Valid Anagram

🔗 NeetCode Problem:
https://neetcode.io/problems/is-anagram/question?list=neetcode150

🔗 LeetCode Problem:
https://leetcode.com/problems/valid-anagram/

---

Problem Statement

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

An anagram is a word formed by rearranging the letters of another word, using all the original letters exactly once.

---

Approach 1: Sorting (Simple but Not Optimal)

Idea

Sort both strings and compare them. If they’re equal after sorting, they’re anagrams.

Pseudocode

• Sort string s
• Sort string t
• Compare if sorted strings are equal

Time Complexity

• O(n log n) → Due to sorting

Why it’s not optimal?

Sorting takes extra time. For anagrams, we only need to count characters, not arrange them.

---

Optimized Approach 1: Using Hash Map (Unordered Map)

Idea

Count the frequency of each character in both strings using hash maps.
If the frequency maps are identical, the strings are anagrams.

Key Insight

We can compare character frequencies without rearranging.

C++ Implementation

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) 
            return false;
        
        unordered_map<char, int> counter_of_s;
        for (int i = 0; i < s.size(); i++) 
            counter_of_s[s[i]]++;
        
        unordered_map<char, int> counter_of_t;
        for (int i = 0; i < t.size(); i++) 
            counter_of_t[t[i]]++;
        
        if (counter_of_s == counter_of_t) 
            return true;
        
        return false;
    }
};

Complexity Analysis

• Time Complexity: O(n) → Single pass through each string
• Space Complexity: O(1) → Max 26 characters (lowercase English letters)

---

Optimized Approach 2: Using Frequency Array (Most Optimal)

Idea

Use a fixed-size array of 26 (for lowercase English letters) to count frequencies.
Increment for characters in s, decrement for characters in t.
If any count goes negative, they’re not anagrams.

Key Insight

Since we only have 26 possible lowercase letters, an array is more efficient than a hash map.

C++ Implementation

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) 
            return false;
        
        vector<int> freq(26, 0);
        
        // Count characters in s
        for (char ch : s) 
            freq[ch - 'a']++;
        
        // Decrement for characters in t
        for (char ch : t) {
            freq[ch - 'a']--;
            if (freq[ch - 'a'] < 0) 
                return false;
        }
        
        return true;
    }
};

Complexity Analysis

• Time Complexity: O(n) → Two passes through the strings
• Space Complexity: O(1) → Fixed array of 26 elements

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Pros	Cons
Sorting	O(n log n)	O(1)	Simple	Slower
Hash Map	O(n)	O(1)*	Flexible for any characters	More memory per hash
Frequency Array	O(n)	O(1)	Most efficient	Limited to 26 letters

*Space is technically O(k) where k is unique characters, but for English letters it’s O(1).

---

Why Frequency Array is Most Optimal

1. Fixed size: Only 26 possible letters
2. No hashing overhead: Direct array indexing is faster
3. Early termination: Can return false immediately if count goes negative
4. Minimal memory: Array of 26 integers vs hash map overhead

---

Example Walkthrough

Example 1: s = "listen", t = "silent"

Using Frequency Array:

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

Processing s = "listen":
freq[11]++ → 'l'
freq[8]++  → 'i'
freq[18]++ → 's'
freq[19]++ → 't'
freq[4]++  → 'e'
freq[13]++ → 'n'

Processing t = "silent":
freq[18]-- → 's' (freq[18] = 0) ✓
freq[8]--  → 'i' (freq[8] = 0) ✓
freq[11]-- → 'l' (freq[11] = 0) ✓
freq[4]--  → 'e' (freq[4] = 0) ✓
freq[13]-- → 'n' (freq[13] = 0) ✓
freq[19]-- → 't' (freq[19] = 0) ✓

All counts remain ≥ 0 → Return true

Example 2: s = "hello", t = "world"

s.size() = 5, t.size() = 5 (same length, continue)

Processing s = "hello":
freq[7]++  → 'h'
freq[4]++  → 'e'
freq[11]+= 2 → 'l' (appears twice)
freq[14]++ → 'o'

Processing t = "world":
freq[22]-- → 'w' (freq[22] = -1) ✗ Return false

No character ‘w’ in s, so it goes negative → Not an anagram!

Key Takeaways

• Avoid sorting for this problem (O(n log n) is slower than needed)
• Frequency array is optimal (O(n) time, O(1) space)
• Character counting approach: Count occurrences, don’t rearrange
• Two-pass is efficient: Simple increment/decrement operations
• Early termination: Return false immediately if a character doesn’t match
• Fixed alphabet: For English letters, array is faster than hash map