Find the first substring of a fixed length whose rolling hash equals a target value under a custom base and modulo.
You are given a string s, an integer power, an integer modulo, an integer k, and a target hash value hashValue.
For any substring of length k, compute its hash from left to right using the rule:
where val(c) is 1 for 'a', 2 for 'b', ..., 26 for 'z'.
Return the substring of length k whose hash equals hashValue. If there are multiple, return the one with the smallest starting index.
This problem is designed to be solved efficiently using a rolling hash idea rather than recomputing every substring hash from scratch.
spower, modulo, k, and hashValueAssume 1 <= k <= s.length and all characters in s are lowercase English letters.
k whose hash matches hashValue.s contains only lowercase English letters1 <= k <= |s|modulo|s|Example 1
Input
s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output
"ee"
Explanation
The substring "ee" has hash (5 * * ) mod 20 = 0, so it matches the target hash.
Example 2
Input
s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output
"fbx"
Explanation
Among all length-3 substrings, "fbx" is the leftmost one whose hash equals 32 under the given formula.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.