Hashing / Frequency Map

Rolling Hash (Rabin-Karp)

Compute a hash for the current window of characters. When the window slides, update the hash in O(1) instead of recomputing. If hashes match, verify the actual strings. Used for fast substring search.

O(n + m)

O(1)

How It Works

Rabin-Karp turns substring search into number comparison. Treat each window of m characters as a base-b number modulo a large prime; that single integer is the window's hash. When the window slides one position, subtract the contribution of the outgoing character, multiply by the base, and add the incoming character — an O(1) update instead of re-hashing m characters.

Scanning the text therefore costs O(n) hash updates. When a window's hash equals the pattern's hash, verify with a direct character comparison to rule out collisions. Expected total time is O(n + m), compared with O(n·m) for naive search, and the same rolling idea powers duplicate-substring detection and plagiarism checks.

Step-by-Step Visualization

Search for pattern 'abc' using rolling hash

Window [0..2]

Pattern hash731

Window hash731 → Match!

1/4

Code

Java

static int rabinKarp(String text, String pattern) {
  long base = 26, mod = (long)1e9 + 7;
  int m = pattern.length();
  long pHash = 0, tHash = 0, power = 1;

  for (int i = 0; i < m; i++) {
    pHash = (pHash * base + pattern.charAt(i)) % mod;
    tHash = (tHash * base + text.charAt(i)) % mod;
    if (i > 0) power = (power * base) % mod;
  }

  for (int i = 0; i <= text.length() - m; i++) {
    if (pHash == tHash) return i; // Verify with actual comparison
    if (i < text.length() - m) {
      tHash = ((tHash - text.charAt(i) * power) * base + text.charAt(i + m)) % mod;
      if (tHash < 0) tHash += mod;
    }
  }
  return -1;
}

Tips & Gotchas

1Hash = sum of (char * base^position) mod prime

2When sliding, remove leading char contribution and add trailing

3Use a large prime to minimize hash collisions

Practice Problems

1Repeated DNA Sequences
2Longest Duplicate Substring
3Find the Index of the First Occurrence in a String
4Longest Happy Prefix

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

How does Rabin-Karp compare with KMP for substring search?

KMP guarantees O(n + m) worst case with no false positives, while Rabin-Karp is O(n + m) only in expectation because hash collisions force verification. Rabin-Karp shines when you search for many patterns of the same length at once or need substring fingerprints, whereas KMP is the safer single-pattern choice.

What causes wrong answers in a rolling hash implementation?

The usual culprits are integer overflow and forgetting to verify on hash match. Take every operation modulo a large prime, keep the modulus and base coprime, and always confirm a candidate match by comparing actual characters, or use double hashing to make collisions negligible.