7  Anagrams and Frequency Counting

8 Anagrams and Frequency Counting

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.

8.1 Key Concepts

8.1.1 1. What Makes Two Strings Anagrams?

• Same length
• Same frequency of each character
• Different order of characters

8.1.2 2. Common Approaches

8.1.2.1 a) Sorting Approach

def is_anagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

• Time Complexity: O(n log n) due to sorting
• Space Complexity: O(n) for storing sorted strings

8.1.2.2 b) Frequency Counting with Hash Map

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
        
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    
    for char in t:
        if char not in freq or freq[char] == 0:
            return False
        freq[char] -= 1
    
    return True

• Time Complexity: O(n)
• Space Complexity: O(1) [since the size of the character set is fixed]

8.1.3 3. Variations of Anagram Problems

1. Group Anagrams
2. Find All Anagrams in a String
3. Valid Anagram with One Edit
4. Palindrome Permutation
5. Permutation in String

8.2 Example: Group Anagrams

def group_anagrams(strs):
    anagrams = {}
    for word in strs:
        key = tuple(sorted(word))
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(word)
    return list(anagrams.values())

8.3 Common Pitfalls

1. Not considering case sensitivity
2. Not handling whitespace correctly
3. Forgetting to check string lengths first
4. Not considering Unicode characters

8.4 Practice Problems

1. Valid Anagram
2. Group Anagrams
3. Find All Anagrams in a String
4. Permutation in String
5. Minimum Number of Steps to Make Two Strings Anagram

8.5 Optimization Tips

1. For lowercase English letters, use a fixed-size array of size 26 for frequency counting
2. For Unicode characters, use a dictionary/hash map
3. Early termination when string lengths differ
4. For multiple anagram checks, consider pre-processing the strings