Hashing / Frequency Map

Group Anagrams

Sort each string alphabetically and use the sorted version as a hash map key. All anagrams produce the same sorted key, so they land in the same bucket.

O(n * k log k)

O(n * k)

How It Works

Grouping anagrams means clustering strings that share the same multiset of characters. The trick is a canonical key: transform each string into a form that is identical for all of its anagrams, then use that form as a hash map key. Sorting each string alphabetically works ('eat', 'tea', 'ate' all become 'aet'), as does encoding the character counts into a string like '1a1e1t'.

With n strings of average length k, sorted keys cost O(n · k log k) while count-signature keys cost O(n · k). Either way you beat the brute-force O(n²) pairwise comparison, because the hash map buckets every group in a single pass over the input.

Step-by-Step Visualization

Group anagrams using sorted string as key

eat

tea

tan

ate

nat

bat

Map

aet [eat]

1/3

Code

Java

static List<List<String>> groupAnagrams(String[] strs) {
  Map<String, List<String>> map = new HashMap<>();

  for (String s : strs) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    String key = new String(chars);
    map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
  }

  return new ArrayList<>(map.values());
}

// Example: groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"})
// → [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Tips & Gotchas

1Sort each string to create a canonical key

2All anagrams share the same sorted key

3Use a hash map: sorted string → list of original strings

Practice Problems

1Group Anagrams
2Group Shifted Strings
3Find Resultant Array After Removing Anagrams

About the Hashing / Frequency Map Pattern

Count how often each character appears using a hash map or fixed-size array (26 slots for lowercase letters). Two strings are anagrams if their frequency maps are identical. This solves most character-comparison problems.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

Should I use the sorted string or a count signature as the map key?

A count signature (e.g., '#1#0#2...' over 26 letters) is asymptotically faster at O(k) per string versus O(k log k) for sorting. In practice sorting is simpler to write and fast enough for typical interview constraints, so pick based on the string lengths involved.

Why not hash the raw character counts array directly?

Most languages hash arrays by identity, not contents, so two equal count arrays would land in different buckets. Convert the counts into an immutable value such as a delimited string or tuple before using it as a key.