Anagrams

Concept

Two strings are Anagrams if they use the exact same characters in the exact same quantities, just arranged in a different order.

• Valid: listen and silent
• Valid: triangle and integral
• Invalid: apple and papel (missing a ‘p’)

Because anagrams are fundamentally about “counting characters,” they are perfectly solved using either Sorting or a Frequency Map.

Approach 1: Sorting (The Easy Way)

If two strings are anagrams, sorting them alphabetically will produce the exact same resulting string.

// Time Complexity: O(N log N)
// Space Complexity: O(N) (to create the arrays for sorting)
function isAnagramSort(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
    
    const sortedS = s.split("").sort().join("");
    const sortedT = t.split("").sort().join("");
    
    return sortedS === sortedT;
}

Use this approach when you are in a rush and space complexity isn’t a strict constraint. However, interviewers will almost always ask you to optimize it.

Approach 2: Frequency Array (The Optimal Way)

Instead of sorting, we just count the characters. We can use a single array of size 26 (if the strings are only lowercase English letters).
We iterate through both strings simultaneously: we add 1 to the bucket for characters in String A, and subtract 1 for characters in String B.
If they are true anagrams, every single bucket will perfectly balance out back to exactly 0 at the end.

// Time Complexity: O(N)
// Space Complexity: O(1) (Array is strictly size 26)
function isAnagram(s: string, t: string): boolean {
    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]++; // Add for 's'
        counts[t.charCodeAt(i) - 97]--; // Subtract for 't'
    }
    
    for (let count of counts) {
        if (count !== 0) return false;
    }
    
    return true;
}

Group Anagrams

Problem: Given an array of strings, group the anagrams together. (e.g., ["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]])

This is a classic problem that combines Arrays, Strings, and Hash Maps.
To group things together, we need a Unique Key that represents the anagram.

1. Loop through the array of strings.
2. For each string, generate its “Anagram Signature”. (Usually just sorting the string, eat -> aet, tea -> aet).
3. Use a Hash Map where the Key is the Signature (aet), and the Value is an array of the original strings ["eat", "tea", "ate"].

function groupAnagrams(strs: string[]): string[][] {
    const map = new Map<string, string[]>();
    
    for (let str of strs) {
        // Generate the signature (Sorting is O(K log K) per word)
        const signature = str.split("").sort().join("");
        
        if (!map.has(signature)) {
            map.set(signature, []);
        }
        map.get(signature)!.push(str);
    }
    
    return Array.from(map.values());
}

Interview Questions

Q: In the “Group Anagrams” problem, generating the signature by sorting takes $O(K \log K)$ time per word. How can you optimize the signature generation to be $O(K)$ time per word?
A: Instead of sorting the word to create the signature, you can build the 26-slot frequency array (which takes $O(K)$ time) and serialize it into a string.
For example, the word abbc becomes a frequency array [1, 2, 1, 0, 0, ...]. You join that array with commas: "1,2,1,0,0,...". That comma-separated string becomes the unique Key in the Hash Map. This completely eliminates the sorting step, reducing the total time complexity to strictly $O(N \times K)$.

Q: A problem asks you to find “All Anagrams in a String” (e.g., given s="cbaebabacd", find all anagrams of p="abc"). How do you solve this?
A: This is a combination of a Sliding Window and a Frequency Counter.
You build a frequency array for the target p. Then, you create a Sliding Window of exactly length p.length on the main string s. As the window slides to the right, you update a second frequency array for the current window (adding the new right char, subtracting the old left char). At every step, you compare the two arrays. If they match perfectly, you found an anagram and you save the Left pointer’s index.