String Anagrams

1. Introduction: The Letter Scramble

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. For example, "listen" is an anagram of "silent". "triangle" is an anagram of "integral".

In coding interviews, Anagram problems are the absolute best way for an interviewer to test your understanding of Frequency Maps and State Compression. Because anagrams share the exact same character counts, comparing two strings is no longer about comparing the characters in order; it's about comparing their mathematical footprints.

2. Core Concept: The Frequency Array

How do we check if String A and String B are anagrams?

• Approach 1 (Sorting): Sort both strings. If sort(A) == sort(B), they are anagrams. This takes $O(N \log N)$ time. Easy to write, but not optimal.
• Approach 2 (Hash Map): Count the frequency of every character in A. Then subtract the frequencies using B. If all counts return to exactly 0, they are anagrams. This takes $O(N)$ time and $O(V)$ space.
• Approach 3 (The Array Optimization): If the strings only contain lowercase English letters, we don't need a heavy HashMap. We can use an int[26] array! char - 'a' perfectly maps the letter 'a' to index 0, and 'z' to index 25.

3. Beginner Code Example: Valid Anagram

Problem Statement: (LeetCode 242) Given two strings s and t, return true if t is an anagram of s, and false otherwise.

public class ValidAnagram {
    public boolean isAnagram(String s, String t) {
        // Quick fail: Anagrams MUST be the exact same length
        if (s.length() != t.length()) {
            return false;
        }
        
        // We only need 26 slots for lowercase English letters
        int[] counts = new int[26];
        
        // Pass 1: Build the frequency map for string 's'
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
        }
        
        // Pass 2: Tear down the frequency map with string 't'
        for (int i = 0; i < t.length(); i++) {
            int index = t.charAt(i) - 'a';
            counts[index]--;
            
            // Optimization: If a count drops below 0, 't' has more of this character than 's'!
            if (counts[index] < 0) {
                return false;
            }
        }
        
        // If we survived the loop and the lengths were equal, it's a perfect match
        return true;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$ where $N$ is the length of the strings.
• Space Complexity: $O(1)$ because the integer array is strictly size 26, regardless of how massive the strings get.

4. Intermediate Code Example: Group Anagrams

Problem Statement: (LeetCode 49) Given an array of strings strs, group the anagrams together. You can return the answer in any order. (e.g., ["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]]).

The Insight: If we use a HashMap<String, List<String>>, what should the Key be? The Key must be identical for all anagrams in a group. We can sort the string! "eat", "tea", and "ate" all sort to "aet". We use "aet" as the Key, and append the original strings to the List.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        
        Map<String, List<String>> map = new HashMap<>();
        
        for (String s : strs) {
            // 1. Generate the normalized Key
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            
            // 2. Add the original string to the correct bucket
            map.putIfAbsent(key, new ArrayList<>());
            map.get(key).add(s);
        }
        
        // 3. Return the grouped lists
        return new ArrayList<>(map.values());
    }
}

5. Advanced Code Example: Find All Anagrams in a String

Problem Statement: (LeetCode 438) Given two strings s and p, return an array of all the start indices of p's anagrams in s.

The Insight: This requires combining Anagram logic with a Sliding Window. We maintain a window of exactly length p.length() sliding across s. Instead of checking the window from scratch every time (which takes $O(N \times M)$), we maintain a running int[26] frequency map for the window. As the window slides right, we +1 the new character entering the window, and -1 the old character leaving the window.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FindAllAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
        
        int[] pCount = new int[26];
        int[] windowCount = new int[26];
        
        int windowSize = p.length();
        
        // 1. Populate the target frequency and the FIRST window
        for (int i = 0; i < windowSize; i++) {
            pCount[p.charAt(i) - 'a']++;
            windowCount[s.charAt(i) - 'a']++;
        }
        
        // 2. Check the first window
        if (Arrays.equals(pCount, windowCount)) {
            result.add(0);
        }
        
        // 3. Slide the window across the rest of the string
        for (int i = windowSize; i < s.length(); i++) {
            // Add the new character entering on the right
            windowCount[s.charAt(i) - 'a']++;
            
            // Remove the old character falling out on the left
            windowCount[s.charAt(i - windowSize) - 'a']--;
            
            // Check if the current window matches the target
            // Arrays.equals for an int[26] takes strictly O(1) time!
            if (Arrays.equals(pCount, windowCount)) {
                result.add(i - windowSize + 1);
            }
        }
        
        return result;
    }
}

6. Common Mistakes Beginners Make

1. Using HashMap<Character, Integer> for lowercase strings

   • The Mistake: Writing heavy HashMap logic instead of int[26].
   • Why it's wrong: It's not technically wrong, but it creates massive overhead. Dynamically allocating Integer objects and calculating hash codes is vastly slower than a raw contiguous array in hardware memory. Using int[26] demonstrates senior-level optimization awareness.

2. Comparing int arrays with ==

   • The Mistake: if (pCount == windowCount)
   • Why it's wrong: In Java, arrays are Objects. == checks if they are literally the same array in memory. They aren't.
   • The Fix: Always use Arrays.equals(arr1, arr2) which compares the contents of the arrays.

3. Re-sorting every window

   • The Mistake: In LeetCode 438, extracting substring(i, i+p.length()), sorting it, and comparing it to the sorted p.
   • Why it's wrong: Extracting a substring takes $O(M)$. Sorting it takes $O(M \log M)$. Doing this for every window $N$ times results in $O(N \times M \log M)$, leading to a guaranteed Time Limit Exceeded.

7. Interview Q&A

Q1: How do you handle Unicode characters (e.g., emojis or Chinese characters) instead of just lowercase English? Answer: You can no longer use the int[26] array. You must fall back to a HashMap<Character, Integer>.

Q2: In "Group Anagrams", what if the strings are massive (e.g., length 10,000), making the Sorting step too slow? Answer: We can skip sorting! Instead, we generate the int[26] frequency array for the string. We then serialize that array into a string format, like "1#0#2#0..." where the numbers represent the counts. We use THAT string as the Key in our HashMap. Generating this key takes $O(M)$ instead of $O(M \log M)$.

8. Practice Problems

1. Valid Anagram (LeetCode 242)
   • Goal: Master the int[26] array optimization.
2. Group Anagrams (LeetCode 49)
   • Goal: Master generating normalized Hash Keys.
3. Find All Anagrams in a String (LeetCode 438)
   • Goal: Master Sliding Window + Array comparison.

9. Summary

• The Identifier: An anagram problem is just a frequency counting problem in disguise.
• The Optimization: int[] counts = new int[26]; counts[c - 'a']++;. Memorize this!
• Grouping: To group anagrams, generate a normalized key (either by sorting the string, or by serializing its frequency array) and use it in a HashMap.
• Sliding Anagrams: A fixed-size sliding window mapping +1 on the right and -1 on the left allows continuous $O(1)$ anagram verification.