Group anagrams

2 snippets in Interview Prep

DSAInterview Prep

Anagram Detection

syntax

Two strings are anagrams if they have identical character frequencies.
Approach 1: Sort both and compare.
Approach 2: Build frequency map and compare.

example

// JavaScript
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const freq = {};
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;
  for (const ch of t) {
    if (!freq[ch]) return false;
    freq[ch]--;
  }
  return true;
}

# Python
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in t:
        if freq.get(ch, 0) == 0:
            return False
        freq[ch] -= 1
    return True

output

is_anagram('listen', 'silent') → True

Note Frequency map: O(n) time, O(1) space (bounded by alphabet size). Sorting approach: O(n log n). Always ask: are inputs lowercase only? Unicode? This affects space analysis. Follow-up: find all anagram groups in a list of words.

Group Anagrams

DSA · Hash Maps & Sets

syntax

Use sorted string (or character frequency tuple) as hash map key.
All anagrams produce the same key.

example

// JavaScript
function groupAnagrams(words) {
  const groups = new Map();
  for (const word of words) {
    const key = word.split('').sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return Array.from(groups.values());
}

# Python
def group_anagrams(words):
    groups = {}
    for word in words:
        key = ''.join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

output

group_anagrams(['eat','tea','tan','ate','nat','bat'])
→ [['eat','tea','ate'], ['tan','nat'], ['bat']]

Note Sorting key: O(n * k log k) where k is max word length. Frequency key alternative: O(n * k) but more code. Interviewers may ask for the optimal approach — mention the frequency-tuple key to avoid k log k sorting per word.