String Array Interview Techniq - Rolling Hash Explained in Java – How Rabin-Karp Solves the Substring Problem

Author: Ramesh Vankayala

---

Introduction

Finding whether a substring exists inside a larger string is one of the most common interview problems.

For example:

Text    = HELLOWORLD
Pattern = LOW

Expected Output:

Substring Found

The simplest solution is to compare every possible window character by character. However, this becomes slow for large strings.

The Rabin-Karp algorithm improves this by using a technique called Rolling Hash.

---

Brute Force Approach

We compare every possible window.

HELLOWORLD

HEL
ELL
LLO
LOW
OWO
WOR
ORL
RLD

Every window is compared character by character.

Time Complexity:

O(n × m)

n = Length of Text
m = Length of Pattern

---

Core Idea of Rolling Hash

Instead of comparing every character in every window,

convert every window into a single integer (Hash Value).

If hash values are different,

the strings are definitely different.

Only when hash values are equal do we compare the actual characters.

This reduces unnecessary comparisons.

---

Step 1 – Calculate Pattern Hash

Pattern

LOW

ASCII Values

Character	ASCII
L	76
O	79
W	87

Pattern Hash

76 + 79 + 87 = 242

Store this value.

---

Step 2 – Calculate First Window Hash

Window

HEL

ASCII

Character	ASCII
H	72
E	69
L	76

Hash

72 + 69 + 76 = 217

Compare

217 != 242

Not Found.

Move the window.

---

Step 3 – Rolling Hash

Previous Window

HEL

New Window

ELL

Instead of recalculating

69 + 76 + 76

Reuse the previous hash.

New Hash

= Previous Hash
- Outgoing Character
+ Incoming Character

=217-72+76

=221

This is called Rolling Hash.

---

Step-by-Step Execution

Window	Hash	Pattern Hash	Result
HEL	217	242	No
ELL	221	242	No
LLO	231	242	No
LOW	242	242	Hash Matched

Now compare characters.

L == L

O == O

W == W

Substring Found.

---

Visual Representation

HELLOWORLD

HEL  -> 217

ELL  -> 221

LLO  -> 231

LOW  -> 242

Pattern

LOW ->242

Hash Match

↓

Compare Characters

↓

Substring Found

---

Java Program

public class RollingHashSubstring {

    public static void main(String[] args) {

        String text = "HELLOWORLD";
        String pattern = "LOW";

        int windowSize = pattern.length();

        // Pattern Hash
        int patternHash = 0;
        for (int i = 0; i < windowSize; i++) {
            patternHash += pattern.charAt(i);
        }

        // First Window Hash
        int windowHash = 0;
        for (int i = 0; i < windowSize; i++) {
            windowHash += text.charAt(i);
        }

        System.out.println("Pattern Hash : " + patternHash);
        System.out.println();

        for (int i = 0; i <= text.length() - windowSize; i++) {

            String window = text.substring(i, i + windowSize);

            System.out.println(
                    "Window : " + window +
                    "  Hash : " + windowHash);

            if (windowHash == patternHash) {

                boolean match = true;

                for (int j = 0; j < windowSize; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }

                if (match) {
                    System.out.println();
                    System.out.println("Substring Found at Index : " + i);
                    return;
                }
            }

            // Rolling Hash
            if (i < text.length() - windowSize) {
                windowHash =
                        windowHash
                        - text.charAt(i)
                        + text.charAt(i + windowSize);
            }
        }

        System.out.println("Substring Not Found");
    }
}

---

Program Output

Pattern Hash : 242

Window : HEL  Hash : 217

Window : ELL  Hash : 221

Window : LLO  Hash : 231

Window : LOW  Hash : 242

Substring Found at Index : 3

---

Why Rolling Hash is Faster

Without Rolling Hash

HEL

Calculate Again

ELL

Calculate Again

LLO

Calculate Again

LOW

Every window is calculated from scratch.

With Rolling Hash

Previous Hash

↓

Remove Left Character

↓

Add Right Character

↓

New Hash

Only two arithmetic operations are needed.

---

Important Interview Question

Q: If two different strings have the same hash, what happens?

Example

ABC

Hash =198

CAB

Hash =198

Both hashes are equal, but the strings are different.

This is called a Hash Collision.

Therefore, whenever hashes match, we must verify the actual characters before declaring success.

---

Time Complexity

Approach	Time Complexity
Brute Force	O(n × m)
Rolling Hash (Average)	O(n)
Character Verification	Only when hashes match

---

Interview Tips

• Explain the brute-force solution first.

• Mention its O(n × m) complexity.

• Introduce hashing as a way to compare integers instead of characters.

• Explain the rolling hash formula:

NewHash = OldHash - OutgoingCharacter + IncomingCharacter

• Mention hash collisions and why character verification is required.

• Finally, discuss how Rabin-Karp uses polynomial rolling hashes in real implementations to reduce collisions.

---

Key Takeaways

• A string can be processed just like an array.

• Rolling Hash reuses the previous computation instead of recalculating every window.

• Rabin-Karp combines rolling hash with character verification.

• The technique dramatically reduces repeated work and is a common interview topic at companies like Amazon, Microsoft, Google, Oracle, Walmart, and Wells Fargo.