Rolling Hash and Rabin-Karp: A Practical Guide for String Coding Interviews

String problems are a staple of coding interviews, and many of them hide the same question underneath: "Have I seen this substring before?" Comparing substrings character by character is slow. A rolling hash lets you compare them in O(1) on average, and the Rabin-Karp algorithm turns that idea into a clean pattern-matching solution. Knowing it gives you a strong option when brute force times out and you don't remember KMP. THE IDEA Treat a string as a number in some base (say 31 or 131), taken modulo a large prime. The hash of "abc" is a*B^2 + b*B + c (mod M). When you slide a window one character to the right, you don't recompute everything. You remove the leftmost character's contribution, multiply by the base, and add the new character: new_hash = ((old_hash - left * B^(k-1)) * B + right) mod M Each slide is O(1), so hashing every window of length k in a string of length n is O(n). RABIN-KARP PATTERN MATCHING To find a pattern of length k in a text: 1. Hash the pattern. 2. Hash the first k characters of the text. 3. Slide the window. Whenever the hashes match, confirm with a direct comparison (to guard against collisions). def rabin_karp(text, pat): B, M = 131, (1 << 61) - 1 k, n = len(pat), len(text) if k > n: return -1 hp = ht = 0 for i in range(k): hp = (hp * B + ord(pat[i])) % M ht = (ht * B + ord(text[i])) % M power = pow(B, k - 1, M) for i in range(n - k + 1): if hp == ht and text[i:i+k] == pat: return i if i + k < n: ht = ((ht - ord(text[i]) * power) * B + ord(text[i+k])) % M return -1 WHERE ELSE IT SHOWS UP - Repeated DNA sequences: hash every window of length 10 and look for duplicates in a set. - Longest duplicate substring: binary search on the length, and use rolling hashes to check whether any substring of that length appears twice. This combination is a favorite hard question. - Longest common substring of two strings, with the same binary search plus hashing approach. - Shortest palindrome and some palindrome checks, by comparing forward and reverse hashes. COLLISIONS: WHAT TO SAY Interviewers often ask, "What if two different strings have the same hash?" Good answers: - Always verify a hash match with a direct comparison when correctness matters. - Use a large prime modulus (like 2^61 - 1) or double hashing with two different moduli to make collisions extremely unlikely. - Mention that the expected running time stays linear, but a worst-case adversarial input can degrade it, which is why KMP or Z-algorithm guarantees are sometimes preferred. COMMON BUGS - Negative values after subtraction in languages without Python's modulo behavior. Add M before taking the modulus. - Forgetting to precompute the highest power, B^(k-1). - Overflow in Java or C++ when multiplying two large values; use 64-bit types and a smaller modulus, or unsigned overflow arithmetic intentionally. HOW TO PRESENT IT Start with the brute force O(n*k) comparison, point out that repeated substring comparison is the bottleneck, then introduce the rolling hash as the fix. Walk through a tiny example with a three-letter window so the interviewer can follow the update formula. Explaining this clearly under pressure is the hard part; some candidates practice with tools like Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to keep their reasoning structured. With a little practice, rolling hashes become one of the most versatile tools in your string toolkit.