Find Substring With Given Hash Value

Hard

#1964Time: O(n * k), where `n` is the length of `s` and `k` is the length of the substring. The outer loop runs `n-k+1` times, and the inner loop for hash calculation runs `k` times.Space: O(k) if we create a new substring in each iteration. This can be optimized to O(1) auxiliary space by accessing characters directly from the input string.

Patterns

Sliding Window Rolling Hash Hash Function

Data structures

String

Prompt

The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function:

hash(s, p, m) = (val(s[0]) * p⁰ + val(s[1]) * p¹ + ... + val(s[k-1]) * p^k-1) mod m.

Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26.

You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue.

The test cases will be generated such that an answer always exists.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output: "ee"
Explanation: The hash of "ee" can be computed to be hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0. 
"ee" is the first substring of length 2 with hashValue 0. Hence, we return "ee".

Example 2:

Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output: "fbx"
Explanation: The hash of "fbx" can be computed to be hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32. 
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32. 
"fbx" is the first substring of length 3 with hashValue 32. Hence, we return "fbx".
Note that "bxz" also has a hash of 32 but it appears later than "fbx".

Constraints:

1 <= k <= s.length <= 2 * 10⁴
1 <= power, modulo <= 10⁹
0 <= hashValue < modulo
s consists of lowercase English letters only.
The test cases are generated such that an answer always exists.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, brute-force check of every possible substring. We iterate through all substrings of length k, calculate their hash value individually, and compare it to the target hashValue. The first substring that provides a match is the one we are looking for.

Algorithm

Iterate through the string s with an index i from 0 to s.length() - k.
For each i, consider the substring starting at i of length k.
Calculate the hash of this substring using the given formula.
- To do this, loop from j = 0 to k-1.
- Maintain a variable for power^j, updating it in each step of the inner loop.
- Sum up val(char) * power^j for all characters in the substring, taking the modulo at each step to prevent overflow.
If the calculated hash matches hashValue, return the current substring s.substring(i, i + k).
Since an answer is guaranteed to exist, the loop will always find a match.

Walkthrough

The algorithm iterates through the string s from the first possible starting position 0 up to the last possible one, n-k. For each starting position i, it considers the substring of length k. A nested loop is then used to compute the hash of this substring. Inside the nested loop, we iterate through the k characters of the substring. For each character at index j within the substring, we calculate its value ('a'=1, 'b'=2, etc.) and multiply it by power^j. We maintain a running currentPower variable, which starts at 1 and is multiplied by power (modulo modulo) in each iteration. The term (val * currentPower) is added to a running hash total, which is also kept within the modulo range. If, after processing all k characters, the final hash equals hashValue, we have found our answer and can return the substring immediately. All calculations involving large numbers should use a 64-bit integer type (long in Java) to avoid overflow before applying the modulo operation.

1class Solution {2    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {3        int n = s.length();4        long p = power;5        long m = modulo;6 7        for (int i = 0; i <= n - k; i++) {8            long currentHash = 0;9            long p_pow = 1;10            // Calculate hash for substring s[i...i+k-1]11            for (int j = 0; j < k; j++) {12                long val = s.charAt(i + j) - 'a' + 1;13                currentHash = (currentHash + (val * p_pow)) % m;14                p_pow = (p_pow * p) % m;15            }16            17            if (currentHash == hashValue) {18                return s.substring(i, i + k);19            }20        }21        22        return ""; // Should not be reached as per problem statement23    }24}

Complexity

Time

O(n * k), where `n` is the length of `s` and `k` is the length of the substring. The outer loop runs `n-k+1` times, and the inner loop for hash calculation runs `k` times.

Space

O(k) if we create a new substring in each iteration. This can be optimized to O(1) auxiliary space by accessing characters directly from the input string.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for small inputs.

Cons

The time complexity of O(n*k) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error on larger test cases.

This approach uses the rolling hash technique to achieve a linear time complexity. Instead of recomputing the hash for each substring from scratch, we calculate the hash of a new substring based on the hash of the previous one in constant time. The given hash function has powers of p increasing from left to right. This structure makes it difficult to slide the window from left to right without using modular inverse (which is not always possible). However, by sliding the window from right to left, we can devise an update formula that only uses multiplication, addition, and subtraction, making it efficient and always applicable.

Algorithm

Let n be the length of s.
Pre-compute power^k mod modulo (let's call it powerK) using modular exponentiation. This will be needed for the update step.
Calculate the hash of the rightmost substring s[n-k..n-1] from scratch. This takes O(k) time.
Check if this initial hash matches hashValue. If so, store n-k as the potential answer index.
Iterate with an index i from n-k-1 down to 0. This index i represents the start of the new window.
In each iteration, update the hash from the previous window s[i+1..i+k] to the current window s[i..i+k-1] in O(1) time using the derived update formula: h_new = (p * h_old - p^k * val_old + val_new) mod m.
h_old is the hash of the previous window, val_old is the value of the character leaving the window (s[i+k]), and val_new is the value of the character entering the window (s[i]).
If the new hash matches hashValue, update the answer index to i. Since we iterate from right to left, we always update the index to find the leftmost match.
After the loop, return the substring starting at the final answer index.

Walkthrough

The core of this method is the O(1) hash update. Let h_i be the hash of s[i..i+k-1] and h_{i+1} be the hash of s[i+1..i+k]. The relationship is h_i = (power * h_{i+1} - power^k * val(s[i+k]) + val(s[i])) mod modulo.

The algorithm works as follows:

We first compute power^k mod modulo using modular exponentiation (O(log k) time).
We then compute the hash of the last substring s[n-k..n-1] from scratch (O(k) time).
We check if this hash matches hashValue and initialize our answer index if it does.
We then loop from i = n-k-1 down to 0. In each step, i is the starting index of the new window. We use the hash of the window s[i+1..i+k] (which we have from the previous step) to calculate the hash of the current window s[i..i+k-1] using the update formula. This step takes O(1) time.
During the update, we must be careful with subtractions in modular arithmetic, using (a - b + m) % m to handle potential negative results. All intermediate calculations should use long to prevent overflow.
If the hash of the current window matches hashValue, we update our answer index to i. Because we are iterating from right to left, the last index we find will be the smallest, corresponding to the first substring in the original string.
Finally, we return the substring identified by the answer index.

1class Solution {2    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {3        int n = s.length();4        long p = power;5        long m = modulo;6        long targetHash = hashValue;7 8        long powerK = 1;9        for (int i = 0; i < k; i++) {10            powerK = (powerK * p) % m;11        }12 13        long currentHash = 0;14        long p_pow = 1;15        // Calculate hash of the last window s[n-k...n-1]16        for (int j = 0; j < k; j++) {17            long val = s.charAt(n - k + j) - 'a' + 1;18            currentHash = (currentHash + val * p_pow) % m;19            p_pow = (p_pow * p) % m;20        }21 22        int ansIdx = -1;23        if (currentHash == targetHash) {24            ansIdx = n - k;25        }26 27        // Slide window from right to left28        // i is the start of the new window29        for (int i = n - k - 1; i >= 0; i--) {30            // currentHash is for window s[i+1..i+k]31            // We want to compute hash for s[i..i+k-1]32            long oldCharVal = s.charAt(i + k) - 'a' + 1;33            long newCharVal = s.charAt(i) - 'a' + 1;34 35            // Update hash using formula: h_i = (p * h_{i+1} - p^k * val(s[i+k]) + val(s[i])) mod m36            currentHash = (p * currentHash) % m;37            long termToRemove = (oldCharVal * powerK) % m;38            currentHash = (currentHash - termToRemove + m) % m;39            currentHash = (currentHash + newCharVal) % m;40 41            if (currentHash == targetHash) {42                ansIdx = i;43            }44        }45 46        return s.substring(ansIdx, ansIdx + k);47    }48}

Complexity

Time

O(n), where `n` is the length of `s`. The initial hash calculation takes O(k), and the rolling hash part takes O(n-k). The total time is dominated by O(n). (Note: `power^k` calculation takes O(log k), which is negligible).

Space

O(1) auxiliary space, as we only need a few variables to store the running hash and powers.

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
Optimal solution for this problem.

Cons

The implementation is more complex than the brute-force approach.
The derivation of the correct rolling hash update formula for this specific hash function can be tricky and error-prone.

Solutions

Solution

1class Solution { public String subStrHash ( String s , int power , int modulo , int k , int hashValue ) { long h = 0 , p = 1 ; int n = s . length (); for ( int i = n - 1 ; i >= n - k ; -- i ) { int val = s . charAt ( i ) - 'a' + 1 ; h = (( h * power % modulo ) + val ) % modulo ; if ( i != n - k ) { p = p * power % modulo ; } } int j = n - k ; for ( int i = n - k - 1 ; i >= 0 ; -- i ) { int pre = s . charAt ( i + k ) - 'a' + 1 ; int cur = s . charAt ( i ) - 'a' + 1 ; h = (( h - pre * p % modulo + modulo ) * power % modulo + cur ) % modulo ; if ( h == hashValue ) { j = i ; } } return s . substring ( j , j + k ); } }

1/** * @param {string} s * @param {number} power * @param {number} modulo * @param {number} k * @param {number} hashValue * @return {string} */ var subStrHash = function ( s , power , modulo , k , hashValue ) { power = BigInt ( power ); modulo = BigInt ( modulo ); hashValue = BigInt ( hashValue ); const n = s . length ; let pk = 1 n ; let ac = 0 n ;

1class Solution { public: string subStrHash ( string s , int power , int modulo , int k , int hashValue ) { long long h = 0 , p = 1 ; int n = s . size (); for ( int i = n - 1 ; i >= n - k ; -- i ) { int val = s [ i ] - 'a' + 1 ; h = (( h * power % modulo ) + val ) % modulo ; if ( i != n - k ) { p = p * power % modulo ; } } int j = n - k ; for ( int i = n - k - 1 ; i >= 0 ; -- i ) { int pre = s [ i + k ] - 'a' + 1 ; int cur = s [ i ] - 'a' + 1 ; h = (( h - pre * p % modulo + modulo ) * power % modulo + cur ) % modulo ; if ( h == hashValue ) { j = i ; } } return s . substr ( j , k ); } };

1class Solution : def subStrHash ( self , s : str , power : int , modulo : int , k : int , hashValue : int ) -> str : h , n = 0 , len ( s ) p = 1 for i in range ( n - 1 , n - 1 - k , - 1 ): val = ord ( s [ i ]) - ord ( "a" ) + 1 h = (( h * power ) + val ) % modulo if i != n - k : p = p * power % modulo j = n - k for i in range ( n - 1 - k , - 1 , - 1 ): pre = ord ( s [ i + k ]) - ord ( "a" ) + 1 cur = ord ( s [ i ]) - ord ( "a" ) + 1 h = (( h - pre * p ) * power + cur ) % modulo if h == hashValue : j = i return s [ j : j + k ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem