Find Substring With Given Hash Value - Practice Coding Problems

Find Substring With Given Hash Value - 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]) * 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.

Input & Output

Example 1 — Basic Case

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

› Output: ee

💡 Note: Hash of "ee" = (5*1 + 5*7) % 20 = 40 % 20 = 0, which matches hashValue

Example 2 — Single Character

$ Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32

› Output: fbx

💡 Note: Hash of "fbx" = (6*1 + 2*31 + 24*961) % 100 = 23130 % 100 = 30, continue checking until match found

Example 3 — Edge Case

$ Input: s = "xmmhdakfursinye", power = 96, modulo = 45, k = 15, hashValue = 21

› Output: xmmhdakfursinye

💡 Note: The entire string has length 15, equal to k, so only one possible substring

Constraints

1 ≤ k ≤ s.length ≤ 2 × 10⁴
1 ≤ power, modulo ≤ 10⁹
0 ≤ hashValue < modulo
s consists of lowercase English letters only
The answer is guaranteed to exist

Visualization

Tap to expand

Understanding the Visualization

Input

String s with parameters: power, modulo, k, hashValue

Process

Compute hash for each substring of length k using rolling hash

Output

Return first substring whose hash equals hashValue

Key Takeaway

🎯 Key Insight: Rolling hash technique allows efficient O(1) hash updates when sliding the window, avoiding costly recomputation

Asked in

G Google 25 M Microsoft 18 A Amazon 15 f Meta 12

The key insight is using rolling hash to avoid recomputing hash values from scratch. The optimal approach uses reverse sliding window to eliminate modular division issues, achieving O(n) time complexity with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n*k)	O(1)	Check every substring of length k by computing hash from scratch
Rolling Hash (Reverse Sliding Window)	O(n)	O(1)	Use rolling hash technique with reverse traversal to avoid division

Brute Force — Algorithm Steps

Step 1: Iterate through all possible starting positions (0 to n-k)
Step 2: For each position, extract substring of length k
Step 3: Compute hash using the formula: sum of val(char) * power^i mod modulo
Step 4: If hash matches hashValue, return the substring

Visualization

Tap to expand

Step-by-Step Walkthrough

Position 0

Compute hash for first k characters

Position 1

Move to next position, recompute hash

Found Match

Return substring when hash matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s, int power, int modulo, int k, int hashValue) {
    int n = strlen(s);
    char* result = malloc((k + 1) * sizeof(char));
    
    for (int i = 0; i <= n - k; i++) {
        long long currentHash = 0;
        long long powerVal = 1;
        
        // Compute hash for substring starting at i
        for (int j = 0; j < k; j++) {
            int charVal = s[i + j] - 'a' + 1;
            currentHash = (currentHash + charVal * powerVal) % modulo;
            powerVal = (powerVal * power) % modulo;
        }
        
        if (currentHash == hashValue) {
            strncpy(result, s + i, k);
            result[k] = '\0';
            return result;
        }
    }
    
    result[0] = '\0';
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int power, modulo, k, hashValue;
    scanf("%d", &power);
    scanf("%d", &modulo);
    scanf("%d", &k);
    scanf("%d", &hashValue);
    
    char* result = solution(s, power, modulo, k, hashValue);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*k)

We check n-k+1 positions, each requiring O(k) time to compute hash

✓ Linear Growth

Space Complexity

O(1)

Only using variables to store current hash and power values

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

589 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler