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]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-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 * 1041 <= power, modulo <= 1090 <= hashValue < modulos consists of lowercase English letters only.The key idea in #2156 Find Substring With Given Hash Value is to efficiently compute substring hashes using a rolling hash technique. The hash is defined using a polynomial function with a given power and modulo, which means recomputing the hash for every substring would be too slow.
A more optimal strategy uses a sliding window combined with rolling hash. Instead of scanning from left to right, we process the string from right to left so the polynomial hash aligns naturally with the problem’s formula. Maintain a window of length k and update the hash incrementally when characters enter or leave the window. Precomputing powers of the base allows efficient adjustment when the window slides.
Whenever the computed rolling hash equals the target hash value, record the current substring’s starting index. This approach ensures each character is processed once. The overall time complexity is O(n), while auxiliary space remains O(1) aside from a few variables for rolling hash calculations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Rolling Hash | O(n) | O(1) |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
How can we update the hash value efficiently while iterating instead of recalculating it each time?
Use the rolling hash method.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Rolling hash allows you to update the hash value of a substring in constant time when the window shifts. This avoids recomputing the hash from scratch and reduces the time complexity from O(n*k) to O(n).
Yes, rolling hash and substring hashing problems are common in technical interviews at large tech companies. Questions like this test understanding of string hashing, modular arithmetic, and sliding window optimization.
No complex data structure is required beyond variables for rolling hash computation. The main technique relies on a sliding window and modular arithmetic to maintain the hash efficiently.
The optimal approach uses a rolling hash combined with a sliding window. By traversing the string from right to left, the hash formula aligns naturally with the polynomial definition, allowing efficient updates as the window moves.