Watch 6 video solutions for Find Substring With Given Hash Value, a hard level problem involving String, Sliding Window, Rolling Hash. This walkthrough by Coding Decoded has 2,299 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given a string and parameters of a polynomial hash function. The task is to find the leftmost substring of length k whose computed hash equals a given hashValue. The hash is defined using powers of power modulo modulo, so efficient substring hashing is required.
Approach 1: Iterative Approach Using Arrays (Rolling Hash + Sliding Window) (Time: O(n), Space: O(1))
This approach evaluates substring hashes using a reverse rolling hash. Instead of recomputing the polynomial hash for every length-k substring, maintain a sliding window from right to left and update the hash incrementally. Multiply the current hash by power, add the new character contribution, and remove the trailing character using precomputed power^k % modulo. The window always represents exactly k characters, and when the computed hash matches hashValue, record the index. This approach leverages sliding window mechanics and modular arithmetic to avoid recomputation. Because each character is processed once, the algorithm runs in O(n) time with constant extra space.
Approach 2: Recursive Approach with Memoization (Time: O(n * k), Space: O(n))
This method computes substring hashes through recursion while caching previously calculated results. Each recursive call builds the polynomial hash by extending the previous substring and storing intermediate results in a memo table. Memoization prevents recomputing hashes for overlapping substrings, which reduces redundant work compared to naive recomputation. However, recursion still requires processing up to k characters when forming a substring hash, making the worst-case complexity O(n * k). The approach is conceptually straightforward for understanding the hash function definition but is less efficient than the iterative rolling hash.
Recommended for interviews: The rolling hash + sliding window solution is the expected approach. It demonstrates understanding of polynomial hashing, modular arithmetic, and efficient window updates. Interviewers typically want to see the O(n) rolling hash optimization after you explain why recomputing hashes for every substring would be too slow.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Rolling Hash + Sliding Window | O(n) | O(1) | Best general solution for large strings; efficient substring hash updates |
| Recursive Hash with Memoization | O(n * k) | O(n) | Useful for understanding polynomial hash construction or recursive DP patterns |