# Find Substring With Given Hash Value
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-substring-with-given-hash-value)
Canonical: https://scaleengineer.com/dsa/problems/find-substring-with-given-hash-value
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
---
## 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`, _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**.

# Approaches
## Brute Force Substring Hashing
This approach involves a straightforward, brute-force check of every possible substring. We iterate through all substrings of length `k`, calculate their hash value individually, and compare it to the target `hashValue`. The first substring that provides a match is the one we are looking for.
**Time:** O(n * k), where `n` is the length of `s` and `k` is the length of the substring. The outer loop runs `n-k+1` times, and the inner loop for hash calculation runs `k` times. · **Space:** O(k) if we create a new substring in each iteration. This can be optimized to O(1) auxiliary space by accessing characters directly from the input string.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** The time complexity of O(n*k) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The algorithm iterates through the string `s` from the first possible starting position `0` up to the last possible one, `n-k`. For each starting position `i`, it considers the substring of length `k`. A nested loop is then used to compute the hash of this substring. Inside the nested loop, we iterate through the `k` characters of the substring. For each character at index `j` within the substring, we calculate its value (`'a'`=1, `'b'`=2, etc.) and multiply it by `power^j`. We maintain a running `currentPower` variable, which starts at 1 and is multiplied by `power` (modulo `modulo`) in each iteration. The term `(val * currentPower)` is added to a running hash total, which is also kept within the `modulo` range. If, after processing all `k` characters, the final hash equals `hashValue`, we have found our answer and can return the substring immediately. All calculations involving large numbers should use a 64-bit integer type (`long` in Java) to avoid overflow before applying the modulo operation.

```java
class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length();
        long p = power;
        long m = modulo;

        for (int i = 0; i <= n - k; i++) {
            long currentHash = 0;
            long p_pow = 1;
            // Calculate hash for substring s[i...i+k-1]
            for (int j = 0; j < k; j++) {
                long val = s.charAt(i + j) - 'a' + 1;
                currentHash = (currentHash + (val * p_pow)) % m;
                p_pow = (p_pow * p) % m;
            }
            
            if (currentHash == hashValue) {
                return s.substring(i, i + k);
            }
        }
        
        return ""; // Should not be reached as per problem statement
    }
}
```
### Algorithm
- Iterate through the string `s` with an index `i` from `0` to `s.length() - k`.
- For each `i`, consider the substring starting at `i` of length `k`.
- Calculate the hash of this substring using the given formula.
  - To do this, loop from `j = 0` to `k-1`.
  - Maintain a variable for `power^j`, updating it in each step of the inner loop.
  - Sum up `val(char) * power^j` for all characters in the substring, taking the modulo at each step to prevent overflow.
- If the calculated hash matches `hashValue`, return the current substring `s.substring(i, i + k)`.
- Since an answer is guaranteed to exist, the loop will always find a match.

## Optimized Rolling Hash (Right-to-Left)
This approach uses the rolling hash technique to achieve a linear time complexity. Instead of recomputing the hash for each substring from scratch, we calculate the hash of a new substring based on the hash of the previous one in constant time. The given hash function has powers of `p` increasing from left to right. This structure makes it difficult to slide the window from left to right without using modular inverse (which is not always possible). However, by sliding the window from right to left, we can devise an update formula that only uses multiplication, addition, and subtraction, making it efficient and always applicable.
**Time:** O(n), where `n` is the length of `s`. The initial hash calculation takes O(k), and the rolling hash part takes O(n-k). The total time is dominated by O(n). (Note: `power^k` calculation takes O(log k), which is negligible). · **Space:** O(1) auxiliary space, as we only need a few variables to store the running hash and powers.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Optimal solution for this problem.
**Cons:** The implementation is more complex than the brute-force approach.; The derivation of the correct rolling hash update formula for this specific hash function can be tricky and error-prone.
### Explanation
The core of this method is the O(1) hash update. Let `h_i` be the hash of `s[i..i+k-1]` and `h_{i+1}` be the hash of `s[i+1..i+k]`. The relationship is `h_i = (power * h_{i+1} - power^k * val(s[i+k]) + val(s[i])) mod modulo`.

The algorithm works as follows:
1. We first compute `power^k mod modulo` using modular exponentiation (O(log k) time).
2. We then compute the hash of the last substring `s[n-k..n-1]` from scratch (O(k) time).
3. We check if this hash matches `hashValue` and initialize our answer index if it does.
4. We then loop from `i = n-k-1` down to `0`. In each step, `i` is the starting index of the new window. We use the hash of the window `s[i+1..i+k]` (which we have from the previous step) to calculate the hash of the current window `s[i..i+k-1]` using the update formula. This step takes O(1) time.
5. During the update, we must be careful with subtractions in modular arithmetic, using `(a - b + m) % m` to handle potential negative results. All intermediate calculations should use `long` to prevent overflow.
6. If the hash of the current window matches `hashValue`, we update our answer index to `i`. Because we are iterating from right to left, the last index we find will be the smallest, corresponding to the first substring in the original string.
7. Finally, we return the substring identified by the answer index.

```java
class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length();
        long p = power;
        long m = modulo;
        long targetHash = hashValue;

        long powerK = 1;
        for (int i = 0; i < k; i++) {
            powerK = (powerK * p) % m;
        }

        long currentHash = 0;
        long p_pow = 1;
        // Calculate hash of the last window s[n-k...n-1]
        for (int j = 0; j < k; j++) {
            long val = s.charAt(n - k + j) - 'a' + 1;
            currentHash = (currentHash + val * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }

        int ansIdx = -1;
        if (currentHash == targetHash) {
            ansIdx = n - k;
        }

        // Slide window from right to left
        // i is the start of the new window
        for (int i = n - k - 1; i >= 0; i--) {
            // currentHash is for window s[i+1..i+k]
            // We want to compute hash for s[i..i+k-1]
            long oldCharVal = s.charAt(i + k) - 'a' + 1;
            long newCharVal = s.charAt(i) - 'a' + 1;

            // Update hash using formula: h_i = (p * h_{i+1} - p^k * val(s[i+k]) + val(s[i])) mod m
            currentHash = (p * currentHash) % m;
            long termToRemove = (oldCharVal * powerK) % m;
            currentHash = (currentHash - termToRemove + m) % m;
            currentHash = (currentHash + newCharVal) % m;

            if (currentHash == targetHash) {
                ansIdx = i;
            }
        }

        return s.substring(ansIdx, ansIdx + k);
    }
}
```
### Algorithm
- Let `n` be the length of `s`.
- Pre-compute `power^k mod modulo` (let's call it `powerK`) using modular exponentiation. This will be needed for the update step.
- Calculate the hash of the rightmost substring `s[n-k..n-1]` from scratch. This takes O(k) time.
- Check if this initial hash matches `hashValue`. If so, store `n-k` as the potential answer index.
- Iterate with an index `i` from `n-k-1` down to `0`. This index `i` represents the start of the new window.
- In each iteration, update the hash from the previous window `s[i+1..i+k]` to the current window `s[i..i+k-1]` in O(1) time using the derived update formula: `h_new = (p * h_old - p^k * val_old + val_new) mod m`.
- `h_old` is the hash of the previous window, `val_old` is the value of the character leaving the window (`s[i+k]`), and `val_new` is the value of the character entering the window (`s[i]`).
- If the new hash matches `hashValue`, update the answer index to `i`. Since we iterate from right to left, we always update the index to find the leftmost match.
- After the loop, return the substring starting at the final answer index.

# Solutions
### Java

```java
class Solution { public String subStrHash ( String s , int power , int modulo , int k , int hashValue ) { long h = 0 , p = 1 ; int n = s . length (); for ( int i = n - 1 ; i >= n - k ; -- i ) { int val = s . charAt ( i ) - 'a' + 1 ; h = (( h * power % modulo ) + val ) % modulo ; if ( i != n - k ) { p = p * power % modulo ; } } int j = n - k ; for ( int i = n - k - 1 ; i >= 0 ; -- i ) { int pre = s . charAt ( i + k ) - 'a' + 1 ; int cur = s . charAt ( i ) - 'a' + 1 ; h = (( h - pre * p % modulo + modulo ) * power % modulo + cur ) % modulo ; if ( h == hashValue ) { j = i ; } } return s . substring ( j , j + k ); } }
```

### JavaScript

```javascript
/** * @param {string} s * @param {number} power * @param {number} modulo * @param {number} k * @param {number} hashValue * @return {string} */ var subStrHash = function ( s , power , modulo , k , hashValue ) { power = BigInt ( power ); modulo = BigInt ( modulo ); hashValue = BigInt ( hashValue ); const n = s . length ; let pk = 1 n ; let ac = 0 n ; 
```

### CPP

```cpp
class Solution { public: string subStrHash ( string s , int power , int modulo , int k , int hashValue ) { long long h = 0 , p = 1 ; int n = s . size (); for ( int i = n - 1 ; i >= n - k ; -- i ) { int val = s [ i ] - 'a' + 1 ; h = (( h * power % modulo ) + val ) % modulo ; if ( i != n - k ) { p = p * power % modulo ; } } int j = n - k ; for ( int i = n - k - 1 ; i >= 0 ; -- i ) { int pre = s [ i + k ] - 'a' + 1 ; int cur = s [ i ] - 'a' + 1 ; h = (( h - pre * p % modulo + modulo ) * power % modulo + cur ) % modulo ; if ( h == hashValue ) { j = i ; } } return s . substr ( j , k ); } };
```

### Python

```python
class Solution : def subStrHash ( self , s : str , power : int , modulo : int , k : int , hashValue : int ) -> str : h , n = 0 , len ( s ) p = 1 for i in range ( n - 1 , n - 1 - k , - 1 ): val = ord ( s [ i ]) - ord ( "a" ) + 1 h = (( h * power ) + val ) % modulo if i != n - k : p = p * power % modulo j = n - k for i in range ( n - 1 - k , - 1 , - 1 ): pre = ord ( s [ i + k ]) - ord ( "a" ) + 1 cur = ord ( s [ i ]) - ord ( "a" ) + 1 h = (( h - pre * p ) * power + cur ) % modulo if h == hashValue : j = i return s [ j : j + k ]
```