String Canonicalization and Grouping

Welcome to our next session. In our previous lessons, we've seen how Map can be used for frequency counting and for value-to-index lookups to find complements. We are progressively uncovering the versatility of hash-based data structures. Today, we'll explore another powerful application: grouping items that share a common property.

The learning outcome for this lesson is to transform strings into canonical keys for grouping equivalent items. This technique is fundamental for a wide range of problems where you need to categorize data based on some inherent, but not immediately obvious, characteristic. We'll anchor our discussion around the classic "Group Anagrams" interview problem, which serves as a perfect illustration of this pattern.

The Problem: Grouping Anagrams

First, let's define the problem, which is LeetCode #49, "Group Anagrams":

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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 instance, if the input is ["eat", "tea", "tan", "ate", "nat", "bat"], the desired output would be [["bat"], ["nat", "tan"], ["eat", "tea", "ate"]].

The core challenge is to identify which strings are anagrams of each other. Strings like "eat", "tea", and "ate" are equivalent in this context because they are all composed of the same letters: one 'a', one 'e', and one 't'. How can we systematically detect this equivalence?

The Core Idea: Canonical Keys

The solution lies in creating a canonical representation for each string—a standardized form that is identical for all anagrams. If we can map every string to such a form, we can use this form as a key in a hash map to group the original strings.

This brings us to our main pattern: Map<CanonicalKey, ListOfOriginalItems>.

There are two primary ways to create a canonical key for anagrams. Let's start with the most intuitive one.

Method 1: Sorting as a Canonical Key

What is a simple transformation that makes "eat", "tea", and "ate" identical? Sorting their characters.

• eat -> aet
• tea -> aet
• ate -> aet

The sorted string "aet" serves as a perfect canonical key. For any other string like "tan", its sorted version is "ant", a different key. This gives us a robust way to identify anagram groups.

The algorithm is as follows:

1. Initialize an empty map, for example groups = new Map<string, string[]>().
2. Iterate through each str in the input array strs.
3. For each str, create its canonical key by sorting its characters: key = str.split('').sort().join('').
4. Check if this key exists in the groups map.
   • If not, create a new entry: groups.set(key, [str]).
   • If it does, retrieve the existing array and push the current str into it: groups.get(key).push(str).
5. After iterating through all strings, the values of the map (groups.values()) are the lists of grouped anagrams.

The following video provides a clear, concise walkthrough of this exact logic and implements it in JavaScript.

TypeScript Implementation & Analysis

Here's a clean TypeScript implementation based on the logic we've just seen.

function groupAnagrams(strs: string[]): string[][] {
    const anagramMap = new Map<string, string[]>();

    for (const str of strs) {
        // 1. Create the canonical key by sorting the string's characters.
        const sortedKey = str.split('').sort().join('');

        // 2. Get the current group for this key, or initialize an empty array if it's the first time.
        if (!anagramMap.has(sortedKey)) {
            anagramMap.set(sortedKey, []);
        }

        // 3. Add the original string to its anagram group.
        anagramMap.get(sortedKey)!.push(str);
    }

    // 4. The values of the map are the grouped anagrams.
    return Array.from(anagramMap.values());
}

Let's analyze the complexity. Let N be the number of strings in the input array, and K be the maximum length of a string.

• Time Complexity: For each of the N strings, we perform a sort, which takes O(K log K) time. The map operations (get, set) are O(1) on average. Therefore, the total time complexity is O(N * K log K).
• Space Complexity: We need to store all the original strings in our map. This requires O(N * K) space.

This is a very solid and common solution. But can we do better? The K log K term from sorting is our main bottleneck.

Method 2: Character Counting as a Canonical Key

Let's reconsider the definition of an anagram: two strings are anagrams if they have the same character counts. This suggests another way to create a canonical key—one that doesn't involve sorting.

If we assume the strings only contain lowercase English letters (a common constraint in these problems), we can represent the character count of any string with a fixed-size array of 26 integers.

For example, for the string "eat":

• We create an array count = [0, 0, ..., 0] of size 26.
• The index 0 corresponds to 'a', 1 to 'b', and so on.
• We iterate through "eat":
  • For 'e', increment count[4].
  • For 'a', increment count[0].
  • For 't', increment count[19].
• The final count array [1, 0, 0, 0, 1, ..., 1, ...] is our new canonical representation. All anagrams of "eat" will produce this exact same array.

This approach has a better time complexity. The following resource provides an excellent explanation.

The time to generate this key for a string of length K is just O(K), since we only need to iterate through the string once. This is an improvement over O(K log K).

A Critical Implementation Detail

There's a catch. In JavaScript (and many other languages), you cannot use an array directly as a Map key, because arrays are mutable objects and are compared by reference, not by value.
[1, 2] !== [1, 2]

To use our count array as a key, we must first convert it into an immutable, hashable format, like a string. A robust way to do this is to join the array elements with a separator.

const key = count.join('#'); // e.g., "1#0#0#0#1#...#1..."

The separator is important to avoid ambiguity. For example, without a separator, a count of [1, 11] and [11, 1] could both become the string "111", leading to incorrect groupings.

The NeetCode video below masterfully explains this counting approach, its complexity benefits, and the implementation details in Python (which translate directly to JS/TS concepts).

TypeScript Implementation & Analysis (Counting Method)

function groupAnagramsWithCount(strs: string[]): string[][] {
    const anagramMap = new Map<string, string[]>();

    for (const str of strs) {
        // 1. Create a frequency count array of size 26.
        const count = new Array(26).fill(0);
        for (const char of str) {
            // Map character 'a' to index 0, 'b' to 1, etc.
            const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
            count[index]++;
        }

        // 2. Create a hashable canonical key from the count array.
        const key = count.join('#');

        // 3. Group the string using this key.
        if (!anagramMap.has(key)) {
            anagramMap.set(key, []);
        }
        anagramMap.get(key)!.push(str);
    }

    return Array.from(anagramMap.values());
}

• Time Complexity: For each of the N strings, we iterate through its K characters to build the count array. This is O(K). Creating the key string from the count array takes constant time (O(26)). The total time complexity is O(N * K).
• Space Complexity: The space required is still O(N * K) to store the map and its values.

Conclusion

Today, we've tackled a common problem type by applying the canonical key pattern. This powerful idea allows us to group items based on an equivalence property by first transforming them into a standardized representation.

Key Takeaways:

• Canonical Representation: The core pattern is to find a transformation that makes all "equivalent" items identical. This transformed version becomes the key in a hash map for grouping.
• Two Methods for Anagrams:
  1. Sorting: Intuitive and easy to implement. O(N * K log K) time complexity.
  2. Character Counting: More efficient, with O(N * K) time complexity. This is often the expected optimal solution in an interview context.
• Hashable Keys: When using complex data (like an array) as a key, you must convert it to an immutable, hashable type (like a string). Pay attention to formatting to avoid key collisions.

This pattern extends far beyond strings and anagrams. Whenever a problem asks you to "group by X" or "find items with property Y," ask yourself: "Can I create a canonical key that represents property Y?"

In our next lesson, we will shift gears from hash maps to a different but equally powerful array-based technique: prefix sums. This will enable us to answer range-based queries on an array with remarkable efficiency.