Anagram Problems: Patterns and Solutions

Two strings are anagrams if they contain exactly the same characters in the same frequencies, just rearranged. “listen” and “silent” are anagrams. “triangle” and “integral” are anagrams. The concept is simple, but the problems built on it range from easy warm-ups to challenging sliding window puzzles.

Anagram problems test your ability to think in terms of character frequencies rather than character order. Once you internalize that shift, most variants become straightforward.

1. Valid anagram

The most basic anagram problem (LeetCode 242): given two strings s and t, determine if t is an anagram of s.

Approach 1: Sorting

If two strings are anagrams, sorting them produces the same result:

def is_anagram_sort(s: str, t: str) -> bool:
    """Check anagram by sorting. O(n log n) time, O(n) space."""
    return sorted(s) == sorted(t)

Simple, but sorting costs O(n log n). We can do better.

Approach 2: Frequency counting with Counter

from collections import Counter

def is_anagram_counter(s: str, t: str) -> bool:
    """Check anagram using Counter. O(n) time, O(1) space (26 letters max)."""
    return Counter(s) == Counter(t)

Time complexity: O(n) — we scan each string once. Space complexity: O(1) — at most 26 lowercase letters in the frequency map.

Approach 3: Single frequency array

For maximum efficiency, use a single array and increment for one string, decrement for the other:

def is_anagram_array(s: str, t: str) -> bool:
    """Check anagram with a single frequency array. O(n) time, O(1) space."""
    if len(s) != len(t):
        return False

    freq = [0] * 26
    for i in range(len(s)):
        freq[ord(s[i]) - ord('a')] += 1
        freq[ord(t[i]) - ord('a')] -= 1

    return all(f == 0 for f in freq)

This uses exactly one pass and a fixed-size array. It’s the cleanest solution for interviews.

Follow-up: Unicode characters

If the input can contain Unicode characters (not just lowercase a-z), you can’t use a fixed array. Fall back to Counter:

def is_anagram_unicode(s: str, t: str) -> bool:
    """Handle Unicode anagrams. O(n) time, O(k) space where k = unique chars."""
    if len(s) != len(t):
        return False
    freq = {}
    for c in s:
        freq[c] = freq.get(c, 0) + 1
    for c in t:
        freq[c] = freq.get(c, 0) - 1
        if freq[c] < 0:
            return False
    return True

2. Group anagrams

LeetCode 49 asks: given a list of strings, group the anagrams together. For example, ["eat","tea","tan","ate","nat","bat"] becomes [["eat","tea","ate"],["tan","nat"],["bat"]].

Approach 1: Sorted string as key

Two strings are anagrams if and only if their sorted versions are equal. Use the sorted string as a hash map key:

from collections import defaultdict

def group_anagrams_sorted(strs: list) -> list:
    """Group anagrams using sorted key. O(n * k log k) time."""
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Time complexity: O(n * k log k) where n is the number of strings and k is the maximum string length. Space complexity: O(n * k) for the hash map.

Approach 2: Frequency tuple as key

Instead of sorting, compute a frequency tuple. This avoids the k log k sorting cost:

def group_anagrams_freq(strs: list) -> list:
    """Group anagrams using frequency tuple key. O(n * k) time."""
    groups = defaultdict(list)
    for s in strs:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
        key = tuple(freq)
        groups[key].append(s)
    return list(groups.values())

Time complexity: O(n * k) — strictly better than sorting when k is large. Space complexity: O(n * k).

Which approach to use?

In practice, the sorted approach is more readable and often fast enough. The frequency approach is theoretically better for long strings. In an interview, mention both and let the interviewer choose.

3. Find all anagrams in a string

LeetCode 438 asks: given a string s and a pattern p, find all start indices of p’s anagrams in s. For example, s = "cbaebabacd", p = "abc" returns [0, 6].

This is a classic fixed-size sliding window problem.

The sliding window approach

Maintain a window of size len(p) sliding over s. Track the character frequencies in the current window and compare with the frequencies of p:

from collections import Counter

def find_anagrams(s: str, p: str) -> list:
    """Find all anagram start indices. O(n) time, O(1) space."""
    result = []
    p_len, s_len = len(p), len(s)

    if p_len > s_len:
        return result

    p_count = Counter(p)
    window_count = Counter(s[:p_len])

    if window_count == p_count:
        result.append(0)

    for i in range(p_len, s_len):
        # Add new character to window
        window_count[s[i]] += 1
        # Remove old character from window
        old_char = s[i - p_len]
        window_count[old_char] -= 1
        if window_count[old_char] == 0:
            del window_count[old_char]

        if window_count == p_count:
            result.append(i - p_len + 1)

    return result

Time complexity: O(n) — each character is added and removed from the window exactly once. Comparing Counters is O(1) because the alphabet size is bounded. Space complexity: O(1) — the Counters hold at most 26 entries.

Optimized with match counting

Comparing entire Counters at each step works but can be made more explicit with a match count:

def find_anagrams_optimized(s: str, p: str) -> list:
    """Find all anagram indices using match counting. O(n) time."""
    result = []
    p_len, s_len = len(p), len(s)
    if p_len > s_len:
        return result

    p_freq = [0] * 26
    w_freq = [0] * 26

    for c in p:
        p_freq[ord(c) - ord('a')] += 1

    matches = 0  # Number of characters with matching frequencies

    # Count initial matches
    for i in range(26):
        if p_freq[i] == 0:
            matches += 1  # Both are 0, they match

    for i in range(s_len):
        # Add character at position i
        idx = ord(s[i]) - ord('a')
        w_freq[idx] += 1
        if w_freq[idx] == p_freq[idx]:
            matches += 1
        elif w_freq[idx] == p_freq[idx] + 1:
            matches -= 1

        # Remove character leaving the window
        if i >= p_len:
            idx = ord(s[i - p_len]) - ord('a')
            w_freq[idx] -= 1
            if w_freq[idx] == p_freq[idx]:
                matches += 1
            elif w_freq[idx] == p_freq[idx] - 1:
                matches -= 1

        if matches == 26:
            result.append(i - p_len + 1)

    return result

This avoids comparing entire frequency arrays at each step — instead, we maintain a running count of how many of the 26 characters have matching frequencies. When all 26 match, we’ve found an anagram.

4. Minimum window substring

LeetCode 76 is one of the hardest sliding window problems. Given strings s and t, find the minimum window in s that contains all characters of t (including duplicates).

This isn’t strictly an anagram problem — the window can contain extra characters — but it builds on the same frequency-counting foundation.

Variable-size sliding window

Use two pointers: expand the right pointer to include characters, and contract the left pointer to minimize the window:

from collections import Counter

def min_window(s: str, t: str) -> str:
    """Minimum window substring. O(n + m) time, O(m) space."""
    if not s or not t or len(s) < len(t):
        return ""

    t_count = Counter(t)
    required = len(t_count)  # Number of unique chars we need

    formed = 0  # Number of unique chars with desired frequency
    window_counts = {}

    best_len = float('inf')
    best_start = 0

    left = 0
    for right in range(len(s)):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1

        # Check if current character's frequency matches requirement
        if char in t_count and window_counts[char] == t_count[char]:
            formed += 1

        # Contract the window from the left
        while formed == required:
            # Update best window
            window_len = right - left + 1
            if window_len < best_len:
                best_len = window_len
                best_start = left

            # Remove leftmost character
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in t_count and window_counts[left_char] < t_count[left_char]:
                formed -= 1
            left += 1

    return s[best_start:best_start + best_len] if best_len != float('inf') else ""

Time complexity: O(n + m) where n = len(s) and m = len(t). Each character is visited at most twice (once by right, once by left). Space complexity: O(m) for the frequency maps.

Understanding the two-pointer movement

The key insight is that once we have a valid window (all characters of t are present), we try to shrink it from the left. We only stop shrinking when the window becomes invalid again. Then we expand from the right to find the next valid window.

# Example walkthrough: s = "ADOBECODEBANC", t = "ABC"
# Right expands until window "ADOBEC" contains A, B, C
# Left shrinks: "DOBEC" loses A -> invalid, record "ADOBEC" (length 6)
# Right expands until "DOBECODEBA" has A, B, C again
# Left shrinks: "BECODEBA" still valid, "ECODEBA" still valid, ...
# Eventually find "BANC" (length 4) — the answer

5. Permutation in string

LeetCode 567: given s1 and s2, return True if s2 contains a permutation (anagram) of s1. This is essentially “find all anagrams” but you only need to find one:

def check_inclusion(s1: str, s2: str) -> bool:
    """Check if s2 contains a permutation of s1. O(n) time."""
    if len(s1) > len(s2):
        return False

    s1_freq = [0] * 26
    window_freq = [0] * 26

    for c in s1:
        s1_freq[ord(c) - ord('a')] += 1

    for i in range(len(s2)):
        window_freq[ord(s2[i]) - ord('a')] += 1

        if i >= len(s1):
            window_freq[ord(s2[i - len(s1)]) - ord('a')] -= 1

        if window_freq == s1_freq:
            return True

    return False

6. Anagram mapping and counting

Count anagram occurrences with Counter

Sometimes you need to count how many words in a list are anagrams of a target:

from collections import Counter

def count_anagram_occurrences(words: list, target: str) -> int:
    """Count how many words are anagrams of target. O(n * k) time."""
    target_freq = Counter(target)
    count = 0
    for word in words:
        if Counter(word) == target_freq:
            count += 1
    return count

Find anagram pairs

Count the total number of anagram pairs in a list:

from collections import defaultdict
from math import comb

def anagram_pairs(words: list) -> int:
    """Count total anagram pairs. O(n * k log k) time."""
    groups = defaultdict(int)
    for word in words:
        key = tuple(sorted(word))
        groups[key] += 1

    total = 0
    for count in groups.values():
        total += comb(count, 2)  # Choose 2 from the group
    return total

Big-O summary

Problem	Time	Space
Valid anagram (sort)	O(n log n)	O(n)
Valid anagram (count)	O(n)	O(1)
Group anagrams (sorted key)	O(n * k log k)	O(n * k)
Group anagrams (freq key)	O(n * k)	O(n * k)
Find all anagrams	O(n)	O(1)
Minimum window substring	O(n + m)	O(m)
Permutation in string	O(n)	O(1)

Practice problems

Work through these in order of increasing difficulty:

1. Valid Anagram (LeetCode 242) — Basic frequency counting
2. Group Anagrams (LeetCode 49) — Hash map with clever keys
3. Permutation in String (LeetCode 567) — Fixed-size sliding window
4. Find All Anagrams in a String (LeetCode 438) — Sliding window + frequency matching
5. Minimum Window Substring (LeetCode 76) — Variable-size sliding window
6. Smallest Window Containing All Characters (GFG) — Similar to minimum window
7. Rank Transform of a String (LeetCode 1331) — Sorting with stable ordering
8. Word Pattern (LeetCode 290) — Bijection mapping (related concept)

Key takeaways

• Anagram = same frequency distribution. Train yourself to immediately think “frequency map” when you see the word anagram.
• Counter is your best friend for quick Python solutions, but know how to use a fixed-size array for O(1) space when the alphabet is bounded.
• Fixed-size sliding window is the pattern for “find anagrams in a string” — slide a window of size len(pattern) and compare frequencies.
• Variable-size sliding window handles the harder “minimum window” variant — expand right, contract left, track validity with a counter.
• For grouping, choose between sorted key (simpler) and frequency tuple key (faster for long strings) based on constraints.