String Hashing & Anagrams

String Hashing & Anagrams

Two words are anagrams if one is a rearrangement of the other's letters: "listen" and "silent", "evil" and "vile". Order doesn't matter, only how many of each letter appear. So every anagram problem reduces to the same idea: describe a string by its letter counts (its signature), and compare or group by that signature.

This lesson builds from checking two strings, to grouping many strings, to finding anagrams hidden inside a longer text with a sliding window, and finishes with rolling hashes, the general technique for comparing substrings fast.

Check whether two strings are anagrams

Approach 1: sort both. Anagrams become identical once their letters are sorted.

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] a = s.toCharArray(), b = t.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

O(n log n) time. Simple and hard to get wrong.

Approach 2: count letters. Count up for one string and down for the other. Anagrams cancel out exactly.

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];                    // assumes lowercase a–z
    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;
}

O(n) time and O(1) extra space (26 counters, regardless of length). For Unicode input, a fixed array of 26 doesn't work. Use a HashMap<Integer, Integer> over code points, or an int[] sized to the alphabet you actually expect.

Group anagrams

Give every word a canonical key that all its anagrams share, and group by that key in a hash map:

List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String w : words) {
        groups.computeIfAbsent(signature(w), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

// Option A: sorted letters — "tea" → "aet". O(k log k) per word of length k.
String signature(String w) {
    char[] c = w.toCharArray();
    Arrays.sort(c);
    return new String(c);
}

// Option B: letter counts — "tea" → "a1e1t1" style key. O(k) per word.
String countSignature(String w) {
    int[] count = new int[26];
    for (char ch : w.toCharArray()) count[ch - 'a']++;
    StringBuilder key = new StringBuilder();
    for (int i = 0; i < 26; i++) if (count[i] > 0) key.append((char) ('a' + i)).append(count[i]);
    return key.toString();
}

For n words of length up to k: sorted keys cost O(n · k log k), count keys cost O(n · k). The count key must be unambiguous. Joining raw counts without separators ("11" could be 1,1 or 11) can make different words collide, which is why the letters are included.

Find anagrams inside a longer string: fixed sliding window

Every candidate is a window of length |p|. Slide the window one step at a time: add the entering character, remove the leaving one, and compare counts.

List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (p.length() > s.length()) return result;

    int[] need = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;

    int[] window = new int[26];
    int matches = 0;                         // how many of the 26 letters currently have equal counts
    for (int i = 0; i < 26; i++) if (need[i] == window[i]) matches++;

    int k = p.length();
    for (int right = 0; right < s.length(); right++) {
        int in = s.charAt(right) - 'a';
        if (window[in] == need[in]) matches--;   // was equal, about to change
        window[in]++;
        if (window[in] == need[in]) matches++;

        if (right >= k) {                        // drop the character leaving the window
            int out = s.charAt(right - k) - 'a';
            if (window[out] == need[out]) matches--;
            window[out]--;
            if (window[out] == need[out]) matches++;
        }
        if (matches == 26) result.add(right - k + 1);
    }
    return result;
}

Comparing two 26-element arrays at every step would also be O(n) overall (26 is a constant). Tracking a matches counter makes each step O(1) and shows interviewers you can maintain an invariant incrementally. "Permutation in String" (does s2 contain any anagram of s1?) is the same code, returning true at the first match.

Rolling hash (Rabin–Karp): comparing substrings in O(1)

Letter counts ignore order, which is perfect for anagrams. To find an exact substring, or compare many substrings, you need a fingerprint that respects order. A polynomial rolling hash treats the string as a number in base B, modulo a large prime M:

hash("abc") = (a·B² + b·B + c) mod M

The trick is that you can slide it in O(1): remove the leftmost character's contribution, shift, and add the new character.

static final long B = 131, M = 1_000_000_007L;

List<Integer> search(String text, String pattern) {
    int k = pattern.length(), n = text.length();
    List<Integer> found = new ArrayList<>();
    if (k > n) return found;

    long power = 1;                                         // B^(k-1) mod M, to remove the leftmost char
    for (int i = 1; i < k; i++) power = power * B % M;

    long hp = 0, hw = 0;
    for (int i = 0; i < k; i++) {
        hp = (hp * B + pattern.charAt(i)) % M;
        hw = (hw * B + text.charAt(i)) % M;
    }
    for (int i = 0; ; i++) {
        if (hp == hw && text.regionMatches(i, pattern, 0, k)) found.add(i);   // verify: hashes can collide
        if (i + k >= n) break;
        hw = (hw - text.charAt(i) * power % M + M) % M;      // remove left char (+M keeps it non-negative)
        hw = (hw * B + text.charAt(i + k)) % M;              // add right char
    }
    return found;
}

• Expected O(n + k). Worst case O(n·k) if many hashes collide, which is why every hash match is verified with a real comparison.
• Collisions are possible: different strings can share a hash. Verify matches, or use two independent moduli (a "double hash") where probability matters.
• The same technique powers "longest duplicate substring" (binary search on length + rolling hash) and plagiarism or duplicate-content detection.

Follow-up questions this topic invites — and their answers

Q: Sorting or counting to check anagrams: which is better? A: Counting is O(n) versus O(n log n), and uses constant space for a fixed alphabet. Sorting is simpler, and works for any characters without choosing an alphabet size. For interviews, show counting and mention sorting as the simpler alternative.

Q: What if the strings contain Unicode, or uppercase and punctuation? A: Normalize first (lowercase with a fixed locale, strip non-letters if the problem says so), then count with a HashMap keyed by code point instead of a 26-slot array. Be careful with characters outside the BMP (emoji), which take two chars in Java.

Q: Could you use a hash (like a sum of character codes) as the anagram key? A: Not safely. Simple sums or products collide ("ad" and "bc" have the same sum). Use an exact signature such as sorted letters or explicit counts. If you use a numeric hash for speed, you must still verify candidates exactly.

Q: Why is Rabin–Karp's worst case O(n·k)? A: Every hash collision triggers a character-by-character verification of length k. With a poor hash, or adversarial input designed to collide, that can happen at every position. A large prime modulus, a random base, or double hashing makes this very unlikely in practice.

Q: How would you find the longest substring that appears twice? A: Binary search on the length L. For each L, slide a rolling hash over all substrings of length L, and check for a repeated hash (verifying on match). If a repeat exists at length L, try longer; otherwise shorter. That's O(n log n) expected. Suffix arrays solve it deterministically.