Skip to main content
Talentd

Find Substring With Given Hash Value - Solution & Explanation

HardStringSliding WindowRolling HashHash Function17 min readAsked at: Google
Practice this problem

Problem Statement

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 * 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.

Approach Overview

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 1: Iterative Approach Using Arrays

This method involves using arrays to store intermediate results or states, enabling access to values efficiently. The idea is to iterate through the data, maintaining pertinent calculations which lead to the final solution.

This C solution uses an array to iterate and perform operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Recursive Approach with Memoization

This approach utilizes recursion to break down the problem into smaller sub-problems and employs memoization to avoid redundant calculations. This technique ensures that once a solution to a sub-problem is computed, it is stored for future reference.

This C solution uses recursive calls with memoization to optimize calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Sliding Window + Reverse Traversal

We can maintain a sliding window of length k to calculate the hash value of the substring. Considering that if we traverse the string in the forward order, the calculation of the hash value involves division and modulo operations, which are relatively complicated to handle. Therefore, we can traverse the string in reverse order, so that when calculating the hash value, only multiplication and modulo operations are needed.

First, we calculate the hash value of the last k characters of the string, and then start to traverse the string in reverse order from the end of the string. Each time we calculate the hash value of the current window, if it is equal to the given hash value, we find a substring that meets the conditions and update the starting position of the answer string.

Finally, return the answer string.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach Using Arrays

Time Complexity: O(n)
Space Complexity: O(1)

Recursive Approach with Memoization

Time Complexity: O(n)
Space Complexity: O(n)

Sliding Window + Reverse Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Rolling Hash + Sliding WindowO(n)O(1)Best general solution for large strings; efficient substring hash updates
Recursive Hash with MemoizationO(n * k)O(n)Useful for understanding polynomial hash construction or recursive DP patterns

Video Solution

Find Substring With Given Hash Value| Leeetcode 2156 | Contest 278 | Rolling Hash Technique 🔥 🔥 🔥 • Coding Decoded • 2,306 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Find Substring With Given Hash Value easy or hard?
LeetCode classifies this problem as Hard because it combines polynomial hashing, modular arithmetic, and careful window updates. Understanding rolling hash mechanics is key to deriving the optimal O(n) solution.
Find Substring With Given Hash Value Python/Java solution
Most implementations follow the same rolling hash logic across languages. Compute character values, maintain the polynomial hash while sliding the window, and track the index where the hash equals the target. Python, Java, C++, C#, and JavaScript implementations typically run in O(n) time.
How to solve Find Substring With Given Hash Value in O(n)?
Compute the hash using a reverse rolling hash. Maintain a window of length k and update the hash when adding a new character and removing the oldest character using modular arithmetic. Precompute power^k % modulo to correctly subtract the outgoing character’s contribution.
What is the best approach for Find Substring With Given Hash Value?
The optimal approach uses rolling hash with a sliding window. By scanning the string from right to left and updating the polynomial hash incrementally, you avoid recomputing hashes for every substring. This reduces the complexity to O(n) time and O(1) space.
Is Find Substring With Given Hash Value asked at Google/Amazon/Meta?
Problems involving rolling hash and substring hashing appear frequently in interviews at companies like Google and Amazon. Variants of Rabin–Karp style hashing and substring search are common string algorithm questions.
What data structure is used in Find Substring With Given Hash Value?
The solution mainly relies on rolling hash computation with modular arithmetic and a sliding window over the string. No complex data structures are required beyond simple variables and optional arrays for memoization or power calculations.
What is the time complexity of Find Substring With Given Hash Value?
The optimal rolling hash solution runs in O(n) time because each character contributes to the hash calculation once as the sliding window moves. Space complexity is O(1) aside from the output substring.

Ready to solve this problem?

Practice Find Substring With Given Hash Value with our built-in code editor and test cases.

Practice on FleetCode
Previous

Distinct Echo Substrings