Find Substring With Given Hash Value
HardUpdated: Aug 2, 2025
Practice on:
Problem
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,_thefirst substring of _s of lengthk
such thathash(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.
Examples
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^41 <= power, modulo <= 10^90 <= hashValue < modulosconsists of lowercase English letters only.- The test cases are generated such that an answer always exists.
Solution
Method 1 – Rolling Hash from Right to Left
Intuition
To efficiently compute the hash for every substring of length k, we use a rolling hash technique. By processing the string from right to left, we can update the hash in constant time for each window, avoiding recomputation.
Approach
- Start from the end of the string and move leftwards.
- Maintain the rolling hash for the current window of length k.
- For each window, check if the hash matches hashValue.
- If a match is found, record the substring.
- Return the leftmost (first) such substring.
Code
C++
class Solution {
public:
string subStrHash(string s, int power, int modulo, int k, int hashValue) {
int n = s.size();
long long hash = 0, p = 1;
int ansIdx = -1;
for (int i = n - 1, j = 0; i >= 0; --i) {
hash = (hash * power + (s[i] - 'a' + 1)) % modulo;
if (j >= k) {
hash = (hash - (p * (s[i + k] - 'a' + 1)) % modulo + modulo) % modulo;
} else {
p = (p * power) % modulo;
++j;
}
if (j >= k && hash == hashValue) ansIdx = i;
}
return s.substr(ansIdx, k);
}
};
Go
func subStrHash(s string, power int, modulo int, k int, hashValue int) string {
n := len(s)
hash, p := 0, 1
ansIdx := -1
for i, j := n-1, 0; i >= 0; i-- {
hash = (hash*power + int(s[i]-'a'+1)) % modulo
if j >= k {
hash = (hash - (p*int(s[i+k]-'a'+1))%modulo + modulo) % modulo
} else {
p = (p * power) % modulo
j++
}
if j >= k && hash == hashValue {
ansIdx = i
}
}
return s[ansIdx : ansIdx+k]
}
Java
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
int n = s.length();
long hash = 0, p = 1;
int ansIdx = -1;
for (int i = n - 1, j = 0; i >= 0; --i) {
hash = (hash * power + (s.charAt(i) - 'a' + 1)) % modulo;
if (j >= k) {
hash = (hash - (p * (s.charAt(i + k) - 'a' + 1)) % modulo + modulo) % modulo;
} else {
p = (p * power) % modulo;
++j;
}
if (j >= k && hash == hashValue) ansIdx = i;
}
return s.substring(ansIdx, ansIdx + k);
}
}
Kotlin
class Solution {
fun subStrHash(s: String, power: Int, modulo: Int, k: Int, hashValue: Int): String {
val n = s.length
var hash = 0L
var p = 1L
var ansIdx = -1
var j = 0
for (i in n - 1 downTo 0) {
hash = (hash * power + (s[i] - 'a' + 1)) % modulo
if (j >= k) {
hash = (hash - (p * (s[i + k] - 'a' + 1)) % modulo + modulo) % modulo
} else {
p = (p * power) % modulo
j++
}
if (j >= k && hash == hashValue) ansIdx = i
}
return s.substring(ansIdx, ansIdx + k)
}
}
Python
class Solution:
def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
n = len(s)
hash = 0
p = 1
ans_idx = -1
j = 0
for i in range(n - 1, -1, -1):
hash = (hash * power + (ord(s[i]) - ord('a') + 1)) % modulo
if j >= k:
hash = (hash - (p * (ord(s[i + k]) - ord('a') + 1)) % modulo + modulo) % modulo
else:
p = (p * power) % modulo
j += 1
if j >= k and hash == hashValue:
ans_idx = i
return s[ans_idx:ans_idx + k]
Rust
impl Solution {
pub fn sub_str_hash(s: String, power: i32, modulo: i32, k: i32, hash_value: i32) -> String {
let s = s.as_bytes();
let n = s.len();
let (mut hash, mut p, mut ans_idx, mut j) = (0i64, 1i64, None, 0);
for i in (0..n).rev() {
hash = (hash * power as i64 + (s[i] - b'a' + 1) as i64) % modulo as i64;
if j >= k {
hash = (hash - (p * (s[i + k as usize] - b'a' + 1) as i64) % modulo as i64 + modulo as i64) % modulo as i64;
} else {
p = (p * power as i64) % modulo as i64;
j += 1;
}
if j >= k && hash == hash_value as i64 {
ans_idx = Some(i);
}
}
let idx = ans_idx.unwrap();
String::from_utf8(s[idx..idx + k as usize].to_vec()).unwrap()
}
}
TypeScript
class Solution {
subStrHash(s: string, power: number, modulo: number, k: number, hashValue: number): string {
const n = s.length;
let hash = 0, p = 1, ansIdx = -1, j = 0;
for (let i = n - 1; i >= 0; --i) {
hash = (hash * power + (s.charCodeAt(i) - 96)) % modulo;
if (j >= k) {
hash = (hash - (p * (s.charCodeAt(i + k) - 96)) % modulo + modulo) % modulo;
} else {
p = (p * power) % modulo;
j++;
}
if (j >= k && hash === hashValue) ansIdx = i;
}
return s.substring(ansIdx, ansIdx + k);
}
}
Complexity
- ⏰ Time complexity:
O(n), since we process each character once and update the hash in constant time. - 🧺 Space complexity:
O(1), as only a few variables are used regardless of input size.