Find Substring With Given Hash Value

HARD

Description

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]) * p⁰ + val(s[1]) * p¹ + ... + val(s[k-1]) * p^k-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 * 31²) mod 100 = 23132 mod 100 = 32. 
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31²) 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 * 10⁴
1 <= power, modulo <= 10⁹
0 <= hashValue < modulo
s consists of lowercase English letters only.
The test cases are generated such that an answer always exists.

Approaches

Checkout 2 different approaches to solve Find Substring With Given Hash Value. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Find Substring With Given Hash Value. Click on different languages to view the code.

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 ); } }

Video Solution

Watch the video walkthrough for Find Substring With Given Hash Value

Patterns:

Sliding WindowRolling HashHash Function

Data Structures:

String