Rolling hash (Rabin–Karp)

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Find the piece cab inside abcab. By hand you compare cab against every three-letter window: abc, bca, cab. Each comparison reads up to three letters, so for a text of n letters and a window of k, that is about n × k letter reads. A related question, "does any window of length 10 appear twice in a DNA string of a million letters", would compare every window against every other, which is a million squared.

Build the structure, one piece at a time

Turn each window into a single number, so comparing windows is comparing numbers. Give the letters values a = 1, b = 2, c = 3 and read a window as a base-10 numeral: abc → 1·100 + 2·10 + 3 = 123, bca → 231, cab → 312. This number is a hash of the window.

Computing each hash from scratch still reads k letters. The trick that makes it rolling: when the window slides one step right, the leftmost letter leaves and a new letter enters, and the hash can be updated in constant time.

1. Window 0, abc: 123, computed in full once.
2. Slide to bca: remove the leading a (subtract 1·100 → 23), shift the rest one place (×10 → 230), add the new a (+1 → 231).
3. Slide to cab: (231 − 2·100)·10 + 2 = 312. Equal to the target 312, so cab is a candidate at position 2.

In real code the base is a prime like 31 and every value is taken modulo a large prime, such as 10⁹ + 7, so the numbers stay small. That introduces the last piece: two different windows can, rarely, land on the same remainder, a collision. So when hashes match, compare the actual letters once to confirm.

Why it is correct

The invariant: the current number is exactly the base-B value of the current window. Sliding keeps it true because of plain place-value arithmetic: if the window value is h = c₁B^k−1 + c₂B^k−2 + … + c_k, then (h − c₁B^k−1)·B + c_k+1 is the value of the next window. Taking everything modulo m keeps the same identity, since addition and multiplication respect remainders. Equal windows always give equal hashes, so no occurrence is missed; a verifying comparison on hash matches removes the false positives from collisions.

h_next = ( (h − c₁·B^k−1) · B + c_k+1 ) mod m

Why it is fast

The first window costs k steps; every slide costs a subtraction, a multiplication and an addition, so all n windows cost O(n + k). A letter-by-letter verification only happens on a hash match, and with a large modulus matches are almost always real, so the expected total is O(n). For the DNA question, put each window's hash in a set as you slide: a million insertions, against a million-squared comparisons.

How to recognise it in an interview

Cues: fixed-length windows, "repeated substring", "longest duplicate", comparing many substrings for equality, or a string-matching question where KMP feels heavy. Say: I will hash each window and roll the hash as the window slides, then verify matches. Repeated DNA Sequences is the set-of-window-hashes version. Longest Duplicate Substring binary-searches the window length and uses rolling hashes to test each length. Find the Index of the First Occurrence in a String is Rabin–Karp, the search above.

02The idea in one line

Hash a window; slide by removing the left char and adding the right.

Reach for it when: Repeated DNA sequences, longest duplicate substring, string matching, distinct substrings.

Cost: O(n) expected time.

03The walk-through, step by step

The video works one example: Rolling hash of length-3 windows over 'abcab'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Target hash: 'cab' = 3·100 + 1·10 + 2 = 312
2. Window 0 'abc': 1·100 + 2·10 + 3 = 123, computed in full once
3. Slide: (123 − 1·100)·10 + 1 = 231 for 'bca', O(1)
4. Slide: (231 − 2·100)·10 + 2 = 312 for 'cab', O(1)
5. Hash 312 equals the target: verify the characters, 'cab' found at 2
6. A hash match is only a candidate: compare the characters to rule out collisions
7. Each slide is constant work: O(n) expected for pattern search or duplicate windows

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in String Algorithms: KMP failure function, Reverse-and-build string transforms, Parse with a state machine, Merge / compare two strings in lockstep, Multi-pattern scan with a set of lengths.