2156. Find Substring With Given Hash Value LeetCode Solution
In this guide, you will get 2156. Find Substring With Given Hash Value LeetCode Solution with the best time and space complexity. The solution to Find Substring With Given Hash Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Substring With Given Hash Value
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”.
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 * 104
1 <= power, modulo <= 109
0 <= hashValue < modulo
s consists of lowercase English letters only.
The test cases are generated such that an answer always exists.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2156. Find Substring With Given Hash Value LeetCode Solution in C++
class Solution {
public:
string subStrHash(string s, int power, int modulo, int k, int hashValue) {
long maxPower = 1;
long hash = 0;
int bestLeft = -1;
auto val = [](char c) -> int { return c - 'a' + 1; };
for (int i = s.length() - 1; i >= 0; --i) {
hash = (hash * power + val(s[i])) % modulo;
if (i + k < s.length())
hash = (hash - val(s[i + k]) * maxPower % modulo + modulo) % modulo;
else
maxPower = maxPower * power % modulo;
if (hash == hashValue)
bestLeft = i;
}
return s.substr(bestLeft, k);
}
}; /* code provided by PROGIEZ */
2156. Find Substring With Given Hash Value LeetCode Solution in Java
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
long maxPower = 1;
long hash = 0;
int bestLeft = -1;
for (int i = s.length() - 1; i >= 0; --i) {
hash = (hash * power + val(s.charAt(i))) % modulo;
if (i + k < s.length())
hash = (hash - val(s.charAt(i + k)) * maxPower % modulo + modulo) % modulo;
else
maxPower = maxPower * power % modulo;
if (hash == hashValue)
bestLeft = i;
}
return s.substring(bestLeft, bestLeft + k);
}
private int val(char c) {
return c - 'a' + 1;
}
} // code provided by PROGIEZ
2156. Find Substring With Given Hash Value LeetCode Solution in Python
class Solution:
def subStrHash(
self,
s: str,
power: int,
modulo: int,
k: int,
hashValue: int,
) -> str:
maxPower = pow(power, k, modulo)
hash = 0
def val(c: str) -> int:
return ord(c) - ord('a') + 1
for i, c in reversed(list(enumerate(s))):
hash = (hash * power + val(c)) % modulo
if i + k < len(s):
hash = (hash - val(s[i + k]) * maxPower) % modulo
if hash == hashValue:
bestLeft = i
return s[bestLeft:bestLeft + k] # code by PROGIEZ
