We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Substring With Given Hash Value

Difficulty: Hard

Problem Description

Given a string s and integers power, modulo, k, and hashValue, return the first substring of length k such that its hash value equals hashValue. The hash of a substring is calculated using a specific formula involving the characters' positions in the alphabet.

Key Insights

  • The hash of a substring is computed using a polynomial rolling hash function.
  • The val(s[i]) function maps characters 'a' to 'z' to integers 1 to 26.
  • A sliding window approach can be used to efficiently compute the hash of each substring of length k.
  • Precompute powers of p to avoid recalculating them multiple times.

Space and Time Complexity

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

Solution

To solve the problem, we can utilize a sliding window approach combined with a rolling hash technique. We will compute the hash of the first substring of length k and slide through the string to compute the hash of subsequent substrings efficiently.

  1. Compute the initial hash for the first substring.
  2. Use a loop to slide the window: remove the contribution of the outgoing character and add the contribution of the incoming character.
  3. Compare the computed hash with hashValue.

The solution involves maintaining a running hash value and adjusting it as we move the starting index of the substring.

Code Solutions

def findSubstring(s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
    n = len(s)
    current_hash = 0
    p_pow = 1
    
    # Calculate the hash for the first 'k' length substring
    for i in range(k):
        current_hash = (current_hash + (ord(s[i]) - ord('a') + 1) * p_pow) % modulo
        p_pow = (p_pow * power) % modulo
    
    # Check if the first substring matches hashValue
    if current_hash == hashValue:
        return s[:k]
    
    # Rolling hash for subsequent substrings
    for i in range(k, n):
        # Remove the first character of the previous substring
        current_hash = (current_hash - (ord(s[i - k]) - ord('a') + 1) * (p_pow // power)) % modulo
        current_hash = (current_hash + modulo) % modulo  # to avoid negative values
        
        # Add the new character
        current_hash = (current_hash * power + (ord(s[i]) - ord('a') + 1)) % modulo
        
        # Check if the current hash matches hashValue
        if current_hash == hashValue:
            return s[i - k + 1:i + 1]
    
    return ""  # This return will never be hit as per problem statement
← Back to All Questions