Solving Anagrams and Character Problems with Hash Maps

1. The Frequency Counting Pattern

At the heart of many character-based problems is the idea of frequency counting. Two strings are anagrams if they are permutations of each other. A more precise definition is that they contain the exact same characters with the exact same frequencies.

For example, "listen" and "silent" are anagrams because they both contain:

• one 'l'
• one 'i'
• one 's'
• one 't'
• one 'e'
• one 'n'

This insight allows us to transform a comparison problem into a counting problem. The most natural data structure for this is a hash map, where we can map each character to its frequency (count).

2. Application 1: Valid Anagram (LeetCode 242)

Let's apply this pattern to a foundational interview problem: Valid Anagram.

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

Based on our frequency counting pattern, the logic is straightforward: if the character counts of both strings are identical, they are anagrams.

Implementing the Solution

There are two main ways to implement this using a frequency map:

Method 1: Two Maps

1. Check if len(s) != len(t). If so, return false.
2. Create a frequency map for s.
3. Create a frequency map for t.
4. Compare the two maps. In Python, you can directly compare two dictionaries with ==.

Method 2: One Map (Increment/Decrement)
This is a slightly more optimized approach in terms of space and often preferred in interviews.

1. Check if len(s) != len(t). If so, return false.
2. Create a single frequency map for s (incrementing counts).
3. Iterate through t, decrementing the count for each character in the map.
4. If you encounter a character in t that is not in the map, or if its count in the map is already zero, you can immediately return false.
5. If the loop completes successfully, all counts in the map should be zero. You can verify this to be certain, but if the lengths are equal and you haven't failed yet, they must be anagrams.

Here is the Python code for the two-map approach:

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    countS, countT = {}, {}

    for i in range(len(s)):
        countS[s[i]] = 1 + countS.get(s[i], 0)
        countT[t[i]] = 1 + countT.get(t[i], 0)
    
    return countS == countT

A Note on Optimization: Array as a Frequency Map

For problems constrained to a small, fixed character set (like the 26 lowercase English letters), you can use a fixed-size array instead of a hash map. This is a common optimization that can improve performance. The index for each character is calculated using its ASCII value.

# Array-based frequency map for lowercase English letters
freq = [0] * 26
for char in my_string:
    index = ord(char) - ord('a')
    freq[index] += 1

This is often faster because it avoids the overhead of hash computations and potential collisions. The algomaster.io resource you read earlier also highlights this in its "Variant 4: Fixed-Size Array" section.

The Pythonic Way: collections.Counter

Python's standard library has a specialized dictionary subclass for this exact purpose. As shown in the final part of the NeetCode video, you can solve this in one line. While you should be prepared to code the manual version in an interview, knowing this demonstrates strong library knowledge.

from collections import Counter

def is_anagram_pythonic(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

3. Application 2: Group Anagrams (LeetCode 49)

Now for a more complex variation: Group Anagrams. Instead of just comparing two strings, you need to group an entire list of strings by their anagram relationship.

To solve this, we need a way to generate a canonical key (a unique signature) for each anagram group. All strings that are anagrams of each other must map to the same key.

As the article explains, there are two common ways to create this canonical key:

1. Sorted String: Sort the characters of the string. For example, "eat", "tea", and "ate" all become "aet" when sorted. "aet" serves as the key.

   • Time to create key: O(k log k), where k is the string length.

2. Character Count Signature: Create a frequency count of the characters. To make it hashable, represent it as a tuple. For "eat", the key would be a 26-element tuple like (1, 0, ..., 1, ..., 1, ...) representing one 'a', one 'e', and one 't'.

   • Time to create key: O(k). This is more efficient than sorting for long strings.

Once you have a method for generating the key, the algorithm is:

1. Initialize a hash map, groups = {}, where keys will be canonical keys and values will be lists of strings. A defaultdict(list) is perfect for this.
2. Iterate through each string in the input list.
3. For each string, compute its canonical key.
4. Append the string to the list associated with that key: groups[key].append(string).
5. Finally, return the values of the hash map.

Here's a concise Python implementation using the sorting method and defaultdict:

Conclusion

You've now seen how hash maps are a cornerstone for solving character-based problems, moving from simple presence checks (hash sets) to powerful frequency counting.

Key Takeaways:

• Frequency Counting: The core pattern for anagram and composition-based problems is to count character frequencies.
• Canonical Keys for Grouping: For problems like "Group Anagrams," the key insight is to create a unique signature (canonical key) for each group, such as a sorted string or a character-count tuple.
• Hash Maps are the Tool: Hash maps provide the O(1) average time lookups needed to efficiently map characters to counts or canonical keys to groups.
• Know Your Tradeoffs: Be ready to discuss the time/space complexity of different key-generation strategies (e.g., sorting at O(k log k) vs. counting at O(k)).
• Arrays as Maps: For fixed, small character sets, using a simple array can be a performance optimization over a hash map.

In our next lesson, we will shift gears to explore linear data structures. You'll start by learning how to implement stacks and queues using both arrays and linked lists, focusing on their LIFO (Last-In, First-Out) and FIFO (First-In, First-Out) properties.