Anagram Problems

Overview

Anagrams are strings formed by rearranging the letters of another string (e.g., "listen" and "silent"). Two strings are anagrams if they have the same character frequencies. Anagram problems test your understanding of frequency counting, sliding window, and hash maps.

Common anagram problems include:

• Check if two strings are anagrams
• Group anagrams together
• Find all anagram substrings
• Anagram substring search
• Valid anagram with constraints
• Minimum window containing anagrams

Pattern 1: Check if Two Strings are Anagrams

Determine if two strings have the same character frequencies.

Approach 1: Frequency Map

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Map<string, number>();
  
  // Count characters in s
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Decrement for characters in t
  for (const char of t) {
    const count = freq.get(char);
    if (!count || count === 0) return false;
    freq.set(char, count - 1);
  }
  
  return true;
}

Approach 2: Array (Fixed Alphabet)

function isAnagramArray(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Array(26).fill(0);
  
  for (let i = 0; i < s.length; i++) {
    freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    freq[t.charCodeAt(i) - 'a'.charCodeAt(0)]--;
  }
  
  return freq.every(count => count === 0);
}

Approach 3: Sorting

function isAnagramSort(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  return s.split('').sort().join('') === t.split('').sort().join('');
}

Time: O(n) for frequency, O(n log n) for sorting, Space: O(k) for frequency, O(1) for array

Pattern 2: Group Anagrams

Group strings that are anagrams of each other.

Approach 1: Sort as Key

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  
  for (const str of strs) {
    const key = str.split('').sort().join('');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  
  return Array.from(map.values());
}

Approach 2: Frequency Count as Key

function groupAnagramsFreq(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  
  for (const str of strs) {
    const freq = new Array(26).fill(0);
    for (const char of str) {
      freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    const key = freq.join(',');
    
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key)!.push(str);
  }
  
  return Array.from(map.values());
}

Time: O(n k log k) for sort, O(n k) for frequency, Space: O(n * k)

Pattern 3: Find All Anagrams in a String

Find all starting indices of anagrams of pattern p in string s.

Approach: Sliding window with frequency map.

function findAnagrams(s: string, p: string): number[] {
  const indices: number[] = [];
  const n = s.length;
  const m = p.length;
  
  if (m > n) return indices;
  
  const pFreq = new Map<string, number>();
  const windowFreq = new Map<string, number>();
  
  // Count frequencies in pattern
  for (const char of p) {
    pFreq.set(char, (pFreq.get(char) || 0) + 1);
  }
  
  // Initialize window
  for (let i = 0; i < m; i++) {
    windowFreq.set(s[i], (windowFreq.get(s[i]) || 0) + 1);
  }
  
  // Check if initial window is anagram
  if (mapsEqual(pFreq, windowFreq)) {
    indices.push(0);
  }
  
  // Slide window
  for (let i = m; i < n; i++) {
    // Add right character
    windowFreq.set(s[i], (windowFreq.get(s[i]) || 0) + 1);
    
    // Remove left character
    const leftChar = s[i - m];
    const count = windowFreq.get(leftChar)!;
    if (count === 1) {
      windowFreq.delete(leftChar);
    } else {
      windowFreq.set(leftChar, count - 1);
    }
    
    // Check if window is anagram
    if (mapsEqual(pFreq, windowFreq)) {
      indices.push(i - m + 1);
    }
  }
  
  return indices;
}

function mapsEqual(map1: Map<string, number>, map2: Map<string, number>): boolean {
  if (map1.size !== map2.size) return false;
  for (const [key, value] of map1) {
    if (map2.get(key) !== value) return false;
  }
  return true;
}

Optimized with array:

function findAnagramsArray(s: string, p: string): number[] {
  const indices: number[] = [];
  const n = s.length;
  const m = p.length;
  
  if (m > n) return indices;
  
  const pFreq = new Array(26).fill(0);
  const windowFreq = new Array(26).fill(0);
  
  // Count pattern frequencies
  for (const char of p) {
    pFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }
  
  // Initialize window
  for (let i = 0; i < m; i++) {
    windowFreq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
  }
  
  // Check initial window
  if (arraysEqual(pFreq, windowFreq)) {
    indices.push(0);
  }
  
  // Slide window
  for (let i = m; i < n; i++) {
    // Add right
    windowFreq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    // Remove left
    windowFreq[s.charCodeAt(i - m) - 'a'.charCodeAt(0)]--;
    
    if (arraysEqual(pFreq, windowFreq)) {
      indices.push(i - m + 1);
    }
  }
  
  return indices;
}

function arraysEqual(arr1: number[], arr2: number[]): boolean {
  return arr1.length === arr2.length && arr1.every((val, idx) => val === arr2[idx]);
}

Time: O(n), Space: O(k) where k is alphabet size

Pattern 4: Valid Anagram with Constraints

Check if two strings are anagrams, handling Unicode and case sensitivity.

function isAnagramUnicode(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Map<string, number>();
  
  // Normalize and count s
  for (const char of s.toLowerCase()) {
    if (/[a-z0-9]/.test(char)) {
      freq.set(char, (freq.get(char) || 0) + 1);
    }
  }
  
  // Decrement t
  for (const char of t.toLowerCase()) {
    if (/[a-z0-9]/.test(char)) {
      const count = freq.get(char);
      if (!count || count === 0) return false;
      freq.set(char, count - 1);
    }
  }
  
  return Array.from(freq.values()).every(count => count === 0);
}

Pattern 5: Minimum Window Containing Anagrams

Find the minimum window in s that contains all characters of t (anagram match).

function minWindowAnagram(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) || 0) + 1);
  }
  
  const window = new Map<string, number>();
  let left = 0, right = 0;
  let valid = 0; // Count of satisfied requirements
  let start = 0, len = Infinity;
  
  while (right < s.length) {
    const c = s[right];
    right++;
    
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) {
        valid++;
      }
    }
    
    while (valid === need.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      
      const d = s[left];
      left++;
      
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--;
        }
        window.set(d, window.get(d)! - 1);
      }
    }
  }
  
  return len === Infinity ? "" : s.substring(start, start + len);
}

Time: O(n), Space: O(k) where k is alphabet size

Pattern 6: Anagram Substring Search (Multiple Patterns)

Find all starting indices where any anagram of any pattern appears.

function findAnagramSubstrings(s: string, patterns: string[]): number[] {
  const indices: number[] = [];
  const patternKeys = new Set<string>();
  
  // Create canonical keys for all patterns
  for (const pattern of patterns) {
    const key = pattern.split('').sort().join('');
    patternKeys.add(key);
  }
  
  const n = s.length;
  const minLen = Math.min(...patterns.map(p => p.length));
  const maxLen = Math.max(...patterns.map(p => p.length));
  
  // Check all possible substrings
  for (let len = minLen; len <= maxLen && len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const substr = s.substring(i, i + len);
      const key = substr.split('').sort().join('');
      
      if (patternKeys.has(key)) {
        indices.push(i);
      }
    }
  }
  
  return indices;
}

Time: O(n m k log k) where m is number of patterns, k is pattern length

Common Variations

Variation 1: Check if String Contains Anagram

Check if any substring of s is an anagram of p.

function containsAnagram(s: string, p: string): boolean {
  return findAnagrams(s, p).length > 0;
}

Variation 2: Count Anagrams

Count how many anagrams of p exist in s.

function countAnagrams(s: string, p: string): number {
  return findAnagrams(s, p).length;
}

Variation 3: Find All Anagrams (Case-Insensitive)

function findAnagramsCaseInsensitive(s: string, p: string): number[] {
  return findAnagrams(s.toLowerCase(), p.toLowerCase());
}

Variation 4: Anagram Pairs

Find all pairs of anagram strings in an array.

function findAnagramPairs(strs: string[]): [string, string][] {
  const pairs: [string, string][] = [];
  
  for (let i = 0; i < strs.length; i++) {
    for (let j = i + 1; j < strs.length; j++) {
      if (isAnagram(strs[i], strs[j])) {
        pairs.push([strs[i], strs[j]]);
      }
    }
  }
  
  return pairs;
}

When to Use These Patterns

Use anagram techniques when:

• Problem asks about "anagram" or "permutation"
• Need to check if strings have same character frequencies
• Finding anagram substrings in a larger string
• Grouping strings by anagram
• Sliding window problems with frequency matching

Template (Anagram Check)

function anagramTemplate(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  
  const freq = new Map<string, number>();
  
  // Count s
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Decrement t
  for (const char of t) {
    const count = freq.get(char);
    if (!count || count === 0) return false;
    freq.set(char, count - 1);
  }
  
  return true;
}

Template (Find Anagrams with Sliding Window)

function findAnagramsTemplate(s: string, p: string): number[] {
  const indices: number[] = [];
  const pFreq = new Map<string, number>();
  const windowFreq = new Map<string, number>();
  
  // Count pattern
  for (const char of p) {
    pFreq.set(char, (pFreq.get(char) || 0) + 1);
  }
  
  // Sliding window
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    windowFreq.set(s[right], (windowFreq.get(s[right]) || 0) + 1);
    
    // Shrink if window too large
    while (right - left + 1 > p.length) {
      const count = windowFreq.get(s[left])!;
      if (count === 1) windowFreq.delete(s[left]);
      else windowFreq.set(s[left], count - 1);
      left++;
    }
    
    // Check if anagram
    if (right - left + 1 === p.length && mapsEqual(pFreq, windowFreq)) {
      indices.push(left);
    }
  }
  
  return indices;
}

Time and Space Complexity Summary

• Check anagram: O(n) time, O(k) space where k is alphabet size
• Group anagrams: O(n k log k) time with sort, O(n k) with frequency
• Find anagrams: O(n) time, O(k) space
• Minimum window: O(n) time, O(k) space

Practice Tips

1. Use frequency maps — Most efficient for anagram checking
2. Choose array vs Map — Array for fixed alphabet (a-z), Map for Unicode
3. Sliding window — Key technique for finding anagram substrings
4. Optimize comparisons — Use arrays for faster equality checks
5. Handle edge cases — Empty strings, different lengths, Unicode

Related Concepts

• Character Frequency Maps — Core technique for anagram problems
• Sliding Window — Used for finding anagram substrings
• Hash Maps — Essential for grouping and counting
• String Sorting — Alternative approach (less efficient)

Anagram problems are excellent for practicing frequency counting and sliding window techniques. Master these patterns, and you'll be well-prepared for anagram-related interview questions.