Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Polynomial Rolling Hash

MEDIUMProblemSolveExternal Links

Description

You are given a string S of length N consisting of lowercase English letters, and two integers Z (the substring length) and K (the base multiplier).

Define a function F on a string of length Z as:

F = S[0] × K⁰ + S[1] × K¹ + S[2] × K² + ... + S[Z-1] × K^(Z-1)

where S[i] denotes the ASCII value of the character at position i (lowercase letters have ASCII values from 97 for 'a' to 122 for 'z').

Your task is to find the maximum value of F among all contiguous substrings of S that have exactly length Z.

Since the value of F may be very large, return the result modulo 10⁹ + 7.

This function F is known as a polynomial rolling hash — a widely used technique in string matching algorithms like Rabin-Karp. The "rolling" property means that when a window of characters slides by one position, the new hash can be computed from the old hash in constant time instead of recomputing from scratch.

Examples

Example 1

Input: S = "nikitasha", N = 9, Z = 6, K = 10

Output: 12597675

Explanation: There are four substrings of length 6:

  • F("nikita") = 110×1 + 105×10 + 107×100 + 105×1000 + 116×10000 + 97×100000 = 10976860
  • F("ikitas") = 105×1 + 107×10 + 105×100 + 116×1000 + 97×10000 + 115×100000 = 12597675
  • F("kitash") = 107×1 + 105×10 + 116×100 + 97×1000 + 115×10000 + 104×100000 = 11659757
  • F("itasha") = 105×1 + 116×10 + 97×100 + 115×1000 + 104×10000 + 97×100000 = 10865965

The maximum is 12597675, which comes from the substring "ikitas".

Example 2

Input: S = "ecdrh", N = 5, Z = 3, K = 9

Output: 10233

Explanation: There are three substrings of length 3:

  • F("ecd") = 101×9⁰ + 99×9¹ + 100×9² = 101 + 891 + 8100 = 9092
  • F("cdr") = 99×9⁰ + 100×9¹ + 114×9² = 99 + 900 + 9234 = 10233
  • F("drh") = 100×9⁰ + 114×9¹ + 104×9² = 100 + 1026 + 8424 = 9550

The maximum is 10233, achieved by the substring "cdr". Notice that 'r' has the highest ASCII value (114) and occupies the highest power position (K²), contributing the most to the hash value.

Example 3

Input: S = "aaa", N = 3, Z = 2, K = 5

Output: 582

Explanation: There are two substrings of length 2:

  • F("aa") = 97×5⁰ + 97×5¹ = 97 + 485 = 582
  • F("aa") = 97×5⁰ + 97×5¹ = 97 + 485 = 582

Both substrings are identical, so the maximum is 582. When all characters are the same, every window produces the same hash.

Constraints

  • 1 ≤ N ≤ 1,000,000
  • 1 ≤ Z ≤ N
  • 1 ≤ K ≤ 2018
  • S consists of lowercase English letters only ('a' to 'z', ASCII 97 to 122)
  • Return the result modulo 10⁹ + 7

Editorial

Brute Force

Intuition

The most natural approach is to directly compute F for every possible substring of length Z, then return the maximum.

Imagine you have a long necklace of lettered beads, and a measuring frame that fits exactly Z beads. You slide the frame one bead at a time from left to right. At each position, you calculate the polynomial value of the beads inside the frame: the first bead's value times K⁰, the second times K¹, the third times K², and so on. After checking every position, you report the highest value you found.

For each window position, we iterate through all Z characters and accumulate the sum S[i+j] × K^j. We maintain K^j incrementally (multiply by K each iteration) to avoid recomputing powers from scratch. After computing F for the current window, we compare it against our running maximum.

This straightforward approach guarantees correctness but does a lot of redundant work — adjacent windows share Z-1 characters, yet we recompute the entire hash for each window independently.

Step-by-Step Explanation

Let's trace through with S = "ecdrh", N = 5, Z = 3, K = 9:

Step 1: Initialize max_F = 0. Total windows = N - Z + 1 = 5 - 3 + 1 = 3.

Step 2: Window 1 at index 0 → substring "ecd".

  • j=0: 'e' has ASCII 101. Term = 101 × 9⁰ = 101 × 1 = 101. Running F = 101.
  • j=1: 'c' has ASCII 99. Term = 99 × 9¹ = 99 × 9 = 891. Running F = 101 + 891 = 992.
  • j=2: 'd' has ASCII 100. Term = 100 × 9² = 100 × 81 = 8100. Running F = 992 + 8100 = 9092.
  • F("ecd") = 9092. Since 9092 > 0, update max_F = 9092.

Step 3: Window 2 at index 1 → substring "cdr".

  • j=0: 'c' = 99 × 1 = 99. Running F = 99.
  • j=1: 'd' = 100 × 9 = 900. Running F = 99 + 900 = 999.
  • j=2: 'r' = 114 × 81 = 9234. Running F = 999 + 9234 = 10233.
  • F("cdr") = 10233. Since 10233 > 9092, update max_F = 10233.

Step 4: Window 3 at index 2 → substring "drh".

  • j=0: 'd' = 100 × 1 = 100. Running F = 100.
  • j=1: 'r' = 114 × 9 = 1026. Running F = 100 + 1026 = 1126.
  • j=2: 'h' = 104 × 81 = 8424. Running F = 1126 + 8424 = 9550.
  • F("drh") = 9550. Since 9550 < 10233, max_F stays 10233.

Step 5: All windows processed. Return max_F = 10233.

Brute Force — Computing Hash for Each Window Independently — Watch how we compute the polynomial hash from scratch for each window of length Z=3, tracking the running sum and maximum across all windows.

Algorithm

  1. Initialize max_F = 0.
  2. For each starting index i from 0 to N - Z:
    a. Initialize F = 0 and K_power = 1.
    b. For each offset j from 0 to Z - 1:
    • Add ASCII(S[i + j]) × K_power to F (take mod).
    • Multiply K_power by K (take mod).
      c. Update max_F = max(max_F, F).
  3. Return max_F.

Code

class Solution {
public:
    long long findMaximum(string &s, int n, int z, int k) {
        long long MOD = 1e9 + 7;
        long long maxF = 0;
        
        for (int i = 0; i <= n - z; i++) {
            long long f = 0;
            long long kPow = 1;
            
            // Compute F for substring s[i..i+z-1]
            for (int j = 0; j < z; j++) {
                f = (f + (long long)s[i + j] * kPow) % MOD;
                kPow = (kPow * k) % MOD;
            }
            
            maxF = max(maxF, f);
        }
        
        return maxF;
    }
};
class Solution:
    def findMaximum(self, s, n, z, k):
        MOD = 10**9 + 7
        max_f = 0
        
        for i in range(n - z + 1):
            f = 0
            k_pow = 1
            
            # Compute F for substring s[i:i+z]
            for j in range(z):
                f = (f + ord(s[i + j]) * k_pow) % MOD
                k_pow = (k_pow * k) % MOD
            
            max_f = max(max_f, f)
        
        return max_f
class Solution {
    long findMaximum(String s, int n, int z, int k) {
        long MOD = 1000000007;
        long maxF = 0;
        
        for (int i = 0; i <= n - z; i++) {
            long f = 0;
            long kPow = 1;
            
            // Compute F for substring s[i..i+z-1]
            for (int j = 0; j < z; j++) {
                f = (f + (long) s.charAt(i + j) * kPow) % MOD;
                kPow = (kPow * k) % MOD;
            }
            
            maxF = Math.max(maxF, f);
        }
        
        return maxF;
    }
}

Complexity Analysis

Time Complexity: O(N × Z)

The outer loop runs (N - Z + 1) times, and for each window the inner loop runs Z times to compute F. Total operations: (N - Z + 1) × Z. In the worst case when Z ≈ N/2, this becomes approximately N²/4, giving O(N²). Each iteration performs a constant number of multiplications and additions modulo M.

Space Complexity: O(1)

We use only a handful of variables (f, kPow, maxF, loop counters). No arrays or data structures that grow with input size.

Why This Approach Is Not Efficient

With N up to 1,000,000 and Z up to N, the brute force performs up to N × Z ≈ 10¹² operations in the worst case. Even at 10⁸ operations per second, this would take roughly 10,000 seconds — far exceeding any reasonable time limit.

The fundamental waste: when the window slides one position right, Z-1 characters remain in the window. Yet we discard all our work and recompute F from scratch for the new window. For example, windows "ecd" and "cdr" share characters 'c' and 'd', but we multiply them by K powers independently in each window.

The key insight is that the polynomial hash function has a rolling property. When we remove one character from the left of the window and add one character on the right, we can mathematically update the old hash to get the new hash in O(1) time — without touching the Z-1 shared characters at all.

If F(i) = S[i]×K⁰ + S[i+1]×K¹ + ... + S[i+Z-1]×K^(Z-1), then:

F(i+1) = (F(i) − S[i]) × K⁻¹ + S[i+Z] × K^(Z-1) (mod M)

Subtract the leaving character's contribution, divide by K to shift all exponents down by one, then add the entering character at the highest power. This transforms an O(Z) per-window computation into O(1) per-window.

Optimal Approach - Sliding Window Rolling Hash

Intuition

Instead of recomputing F for every window, we compute it once for the first window and then roll it forward, updating the hash in constant time as the window slides.

Think of a cash register displaying a running total. When a customer in a queue of Z people is served and leaves (front of the line), and a new person joins at the back, you do not re-scan everyone's bill. Instead, you subtract the leaving person's bill and add the new person's bill. The polynomial hash works similarly, with one extra step: a "shift" to account for the positional weighting.

Here is exactly what happens when the window moves from position i to position i+1:

  1. Subtract the leaving character: Remove S[i] × K⁰ from the hash. This eliminates the contribution of the character that just left the window.
  2. Divide by K (multiply by K⁻¹ mod M): Every remaining character's exponent needs to decrease by 1 (since their relative position within the window shifted left by one). Mathematically, dividing by K achieves this: K¹ becomes K⁰, K² becomes K¹, etc.
  3. Add the entering character at K^(Z-1): The new character enters at the rightmost position of the window, which has the highest power K^(Z-1).

The modular inverse K⁻¹ exists because M = 10⁹+7 is a prime number. We compute it once using Fermat's Little Theorem: K⁻¹ = K^(M-2) mod M, which takes O(log M) time via binary exponentiation.

After one O(Z) computation for the first window and O(log M) precomputation for K⁻¹ and K^(Z-1), every subsequent window takes O(1). Total: O(N).

Diagram showing how the polynomial hash updates when the window slides: subtract leaving character, divide by K, add entering character at highest power
Diagram showing how the polynomial hash updates when the window slides: subtract leaving character, divide by K, add entering character at highest power

Step-by-Step Explanation

Let's trace the sliding window approach on S = "ecdrh", N = 5, Z = 3, K = 9, M = 10⁹+7:

Step 1: Precomputation.

  • K^(Z-1) = 9² = 81.
  • K⁻¹ mod M = 9^(M-2) mod M = 111111112. (Verify: 9 × 111111112 = 1000000008 ≡ 1 mod 10⁹+7.)

Step 2: Compute the first window hash ("ecd").

  • F = 101×1 + 99×9 + 100×81 = 101 + 891 + 8100 = 9092.
  • max_F = 9092.

Step 3: Slide to window "cdr" — identify the leaving and entering characters.

  • Leaving character: S[0] = 'e' (ASCII 101) — exits the left side.
  • Entering character: S[3] = 'r' (ASCII 114) — enters the right side.

Step 4: Subtract the leaving character.

  • F = F - ASCII('e') = 9092 - 101 = 8991.
  • This removes 'e's contribution at the K⁰ position.

Step 5: Multiply by K⁻¹ to shift all exponents down by 1.

  • F = 8991 × K⁻¹ mod M = 8991 × 111111112 mod M.
  • Since 8991 = 9 × 999, and 9 × K⁻¹ = 1, we get F = 999.
  • What happened: 'c' moved from K¹ to K⁰, 'd' moved from K² to K¹.

Step 6: Add the entering character at K^(Z-1).

  • F = 999 + 114 × 81 = 999 + 9234 = 10233.
  • Character 'r' enters at the K² position.

Step 7: Compare with maximum.

  • 10233 > 9092 → update max_F = 10233.

Step 8: Slide to window "drh" — leaving 'c' (99), entering 'h' (104).

  • F = (10233 - 99) × K⁻¹ + 104 × 81.
  • F = 10134 × K⁻¹ + 8424.
  • Since 10134 = 9 × 1126, we get 10134 × K⁻¹ = 1126.
  • F = 1126 + 8424 = 9550.

Step 9: Compare with maximum.

  • 9550 < 10233 → max_F stays 10233.

Step 10: All windows processed. Return max_F = 10233.

Sliding Window Rolling Hash — O(1) Updates — Watch how the hash value updates in constant time as the window slides: subtract the leaving character, shift exponents via modular inverse, and add the entering character.

Algorithm

  1. Precompute constants:
    • K_pow_Z_1 = K^(Z-1) mod M using binary exponentiation.
    • inv_K = K^(M-2) mod M using binary exponentiation (Fermat's Little Theorem, since M is prime).
  2. Compute first window hash:
    • F = Σ(j=0 to Z-1) S[j] × K^j mod M.
    • Set max_F = F.
  3. Slide and roll: For each starting index i from 1 to N-Z:
    • Subtract leaving character: F = (F - ASCII(S[i-1]) + M) mod M.
    • Shift exponents: F = F × inv_K mod M.
    • Add entering character: F = (F + ASCII(S[i+Z-1]) × K_pow_Z_1) mod M.
    • Update max_F = max(max_F, F).
  4. Return max_F.

Code

class Solution {
public:
    long long power(long long base, long long exp, long long mod) {
        long long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp & 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }
    
    long long findMaximum(string &s, int n, int z, int k) {
        long long MOD = 1e9 + 7;
        
        // Precompute K^(Z-1) and modular inverse of K
        long long kPowZ1 = power(k, z - 1, MOD);
        long long invK = power(k, MOD - 2, MOD);
        
        // Compute hash for the first window
        long long f = 0, kPow = 1;
        for (int j = 0; j < z; j++) {
            f = (f + (long long)s[j] * kPow) % MOD;
            kPow = kPow * k % MOD;
        }
        
        long long maxF = f;
        
        // Slide the window using rolling hash
        for (int i = 1; i <= n - z; i++) {
            // 1. Subtract leaving character
            f = (f - s[i - 1] + MOD) % MOD;
            // 2. Shift exponents down by multiplying by K^(-1)
            f = f * invK % MOD;
            // 3. Add entering character at K^(Z-1)
            f = (f + (long long)s[i + z - 1] * kPowZ1) % MOD;
            
            maxF = max(maxF, f);
        }
        
        return maxF;
    }
};
class Solution:
    def findMaximum(self, s, n, z, k):
        MOD = 10**9 + 7
        
        # Precompute K^(Z-1) and modular inverse of K
        k_pow_z1 = pow(k, z - 1, MOD)
        inv_k = pow(k, MOD - 2, MOD)  # Fermat's Little Theorem
        
        # Compute hash for the first window
        f = 0
        k_pow = 1
        for j in range(z):
            f = (f + ord(s[j]) * k_pow) % MOD
            k_pow = (k_pow * k) % MOD
        
        max_f = f
        
        # Slide the window using rolling hash
        for i in range(1, n - z + 1):
            # 1. Subtract leaving character
            f = (f - ord(s[i - 1]) + MOD) % MOD
            # 2. Shift exponents down
            f = f * inv_k % MOD
            # 3. Add entering character at K^(Z-1)
            f = (f + ord(s[i + z - 1]) * k_pow_z1) % MOD
            
            max_f = max(max_f, f)
        
        return max_f
class Solution {
    long power(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }
    
    long findMaximum(String s, int n, int z, int k) {
        long MOD = 1000000007;
        
        // Precompute K^(Z-1) and modular inverse of K
        long kPowZ1 = power(k, z - 1, MOD);
        long invK = power(k, MOD - 2, MOD);
        
        // Compute hash for the first window
        long f = 0, kPow = 1;
        for (int j = 0; j < z; j++) {
            f = (f + (long) s.charAt(j) * kPow) % MOD;
            kPow = kPow * k % MOD;
        }
        
        long maxF = f;
        
        // Slide the window using rolling hash
        for (int i = 1; i <= n - z; i++) {
            // 1. Subtract leaving character
            f = (f - s.charAt(i - 1) + MOD) % MOD;
            // 2. Shift exponents down
            f = f * invK % MOD;
            // 3. Add entering character at K^(Z-1)
            f = (f + (long) s.charAt(i + z - 1) * kPowZ1) % MOD;
            
            maxF = Math.max(maxF, f);
        }
        
        return maxF;
    }
}

Complexity Analysis

Time Complexity: O(N + log M) which simplifies to O(N)

The precomputation phase uses binary exponentiation twice: once for K^(Z-1) in O(log Z) time and once for K^(M-2) in O(log M) ≈ O(30) time. Computing the first window hash takes O(Z) time. The sliding phase processes (N - Z) windows at O(1) each. Total: O(Z + (N - Z) + log M) = O(N + log M). Since M = 10⁹+7 is a fixed constant, log M ≈ 30 is negligible, giving us O(N).

Compared to the brute force O(N × Z), this is a dramatic improvement. For N = 10⁶ and Z = 500,000: brute force does ~5 × 10¹¹ operations vs. ~10⁶ for the rolling hash.

Space Complexity: O(1)

We use a constant number of variables: f, maxF, invK, kPowZ1, and loop counters. No arrays or data structures that scale with input size. The space is the same as the brute force approach.