Hashing / Frequency Map

Anagram Detection

Build a frequency map for both strings. If the maps match, they're anagrams. For O(1) space with lowercase letters, use an int array of size 26.

O(n)

O(1)

How It Works

Two strings are anagrams exactly when they contain the same characters with the same frequencies. Instead of sorting both strings (O(n log n)), build a frequency count: increment counts for one string, decrement for the other, and check that every count returns to zero. For lowercase English letters an int[26] array is enough; a hash map generalizes to Unicode.

The frequency-map idea extends beyond a single comparison: grouping many strings by their canonical count signature clusters all anagrams together in one pass over the input. Because each character is touched a constant number of times, the whole check runs in O(n) time.

Step-by-Step Visualization

Compare 'anagram' vs 'nagaram'

sanagram

tnagaram

1/3

Code

Java

static boolean isAnagram(String s, String t) {
  if (s.length() != t.length()) return false;
  int[] count = new int[26];

  for (int i = 0; i < s.length(); i++) {
    count[s.charAt(i) - 'a']++;
    count[t.charAt(i) - 'a']--;
  }

  for (int c : count) if (c != 0) return false;
  return true;
}

// Example: isAnagram("anagram", "nagaram") → true

Tips & Gotchas

1Two strings are anagrams if they have the same character frequencies

2Use a fixed-size array of 26 for lowercase letters

3Alternatively, sort both strings and compare

Practice Problems

1Valid Anagram
2Group Anagrams
3Find All Anagrams in a String
4Ransom Note

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

Is a frequency array faster than sorting for anagram checks?

Yes. Counting characters runs in O(n) time with O(1) extra space for a fixed alphabet, while sorting both strings costs O(n log n). Sorting is only competitive when strings are tiny or you already need them sorted.

How do I handle Unicode or mixed-case input?

Replace the fixed int[26] array with a hash map keyed by code point, and normalize case first if the comparison should be case-insensitive. The algorithm is otherwise unchanged.

Can I short-circuit before counting?

Always compare lengths first: strings of different lengths can never be anagrams, so you avoid the counting pass entirely. During the decrement pass you can also return false the moment any count goes negative.