Find Substring With Given Hash Value · Interview Problem

Back to problems

Leetcode

Medium

Strings

Math

Hash Maps

Google

Find Substring With Given Hash Value

Find the first substring of a fixed length whose rolling hash equals a target value under a custom base and modulo.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

LeetCode

gfg

Primary

Problem Statement

Problem

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:

hash(t) = (val(t_0) \cdot power^0 + val(t_1) \cdot power^1 + \cdots + val(t_{k-1}) \cdot power^{k-1}) \bmod modulo

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.

Input Format

A lowercase string s
Integers power, modulo, k, and hashValue

Assume 1 <= k <= s.length and all characters in s are lowercase English letters.

Output Format

Return the substring of length k whose hash matches hashValue.
If several substrings match, return the leftmost one.

Constraints

s contains only lowercase English letters
1 <= k <= |s|
Hash values are computed modulo modulo
The expected approach should run in linear time with respect to |s|

Examples

Sample cases returned by the problem API.

Example 1

Input

s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0

Output

"ee"

Explanation

The substring "ee" has hash (5 * $7^{0}+5$ * $7^{1}$ ) 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

Unlock deeper context for this problem

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.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress