LC #242: Valid Anagrams

🧠 Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An anagram uses the same characters and the same frequency, but in any order.

🔗 Leetcode Link

Valid Anagram – LC #242

---

💥 Brute Force

// generate all permutations of s and check if t exists in it
List<String> perms = generatePermutations(s);  
return perms.contains(t);

• Time: O(n!) ← factorial due to permutations
• Space: O(n) or more
  ❌ Not scalable. Just a theoretical baseline.

---

⚡ Optimized: Frequency Count using Array

int[] freqArr = new int[26];                         // fixed-size array for lowercase a–z (O(1) space)

for (char c : s.toCharArray())                       // count frequency of each char in s
    freqArr[c - 'a']++;

for (char c : t.toCharArray()) {                     // decrement frequency for each char in t
    if (freqArr[c - 'a'] < 1) return false;          // char not present or used too many times
    freqArr[c - 'a']--;
}

for (int count : freqArr)                            // final check: all frequencies must be zero
    if (count != 0) return false;

return true;                                         // all matched — valid anagram

• Time: O(n) ← traverse both strings once
• Space: O(1) ← uses 26-sized array for lowercase chars

✅ Simple. Fast. Most interviewer-friendly.

---

🧠 Key Insights

• Anagram = same characters + same frequencies (order doesn't matter)
• Sorting approach works too (Arrays.sort) but is slower → O(n log n)
• Better to count character frequencies → O(n)
• Initially considered 2 HashMaps → works but not optimal
• Use 1 array or 1 HashMap instead — cleaner + space-efficient
• If using array, final check = all values must be 0

• ✅ For lowercase only:

  int[] freq = new int[26];  
  index = c - 'a';
  

• ✅ For alphanumeric (A–Z, a–z, 0–9):
  Total possible chars = 62

  if (Character.isUpperCase(c)) index = c - 'A';           // 0–25  
  else if (Character.isLowerCase(c)) index = c - 'a' + 26; // 26–51  
  else index = c - '0' + 52;                               // 52–61
  

• 🌐 For arbitrary Unicode (e.g., emojis, symbols):
  Use HashMap<Character, Integer> for dynamic char support
  ↪ You lose O(1) space, but gain generality

---

🧪 Dry Run + Test Cases

✅ Test Case 1

Input: s = "aabb", t = "baba"

Steps:

• Count s: a+2, b+2 → freq = [2a, 2b]
• Use t: b–1, a–1, b–1, a–1 → all counts zero
  ✅ Final freq array = all zeros → return true

---

✅ Test Case 2

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

Steps:

• Count s: r+1, a+1, t+1
• Use t: c not in freq → return false
  ❌ Extra char → not an anagram

---

⚠️ Edge Case 1

Input: s = "", t = ""

Steps:

• Both strings empty → no characters to mismatch
  ✅ return true (by definition)

---

⚠️ Edge Case 2

Input: s = "a", t = ""

Steps:

• Count s: a+1
• t is empty → never decrements
  ❌ leftover a in freq → return false

---

🔁 Similar Problems

• Group Anagrams – LC #49
  ↪ Group words that are anagrams → use a HashMap with sorted string or char count as key

• Find All Anagrams in a String – LC #438
  ↪ Sliding window + freq count → find all substrings that are anagrams of a given pattern

• Valid Palindrome – LC #125
  ↪ Normalize and compare → similar pre-processing and cleanup logic

• Ransom Note – LC #383
  ↪ Use char counts to check if one string can construct another

• Longest Palindrome – LC #409
  ↪ Use frequency counting to maximize palindrome length