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,_thefirst substring of _s of lengthk such thathash(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.

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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 * 10^4
  • 1 <= power, modulo <= 10^9
  • 0 <= hashValue < modulo
  • s consists of lowercase English letters only.
  • The test cases are generated such that an answer always exists.

Solution

Method 1 – Rolling Hash from Right to Left

Intuition

To efficiently compute the hash for every substring of length k, we use a rolling hash technique. By processing the string from right to left, we can update the hash in constant time for each window, avoiding recomputation.

Approach

  1. Start from the end of the string and move leftwards.
  2. Maintain the rolling hash for the current window of length k.
  3. For each window, check if the hash matches hashValue.
  4. If a match is found, record the substring.
  5. Return the leftmost (first) such substring.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        int n = s.size();
        long long hash = 0, p = 1;
        int ansIdx = -1;
        for (int i = n - 1, j = 0; i >= 0; --i) {
            hash = (hash * power + (s[i] - 'a' + 1)) % modulo;
            if (j >= k) {
                hash = (hash - (p * (s[i + k] - 'a' + 1)) % modulo + modulo) % modulo;
            } else {
                p = (p * power) % modulo;
                ++j;
            }
            if (j >= k && hash == hashValue) ansIdx = i;
        }
        return s.substr(ansIdx, k);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func subStrHash(s string, power int, modulo int, k int, hashValue int) string {
    n := len(s)
    hash, p := 0, 1
    ansIdx := -1
    for i, j := n-1, 0; i >= 0; i-- {
        hash = (hash*power + int(s[i]-'a'+1)) % modulo
        if j >= k {
            hash = (hash - (p*int(s[i+k]-'a'+1))%modulo + modulo) % modulo
        } else {
            p = (p * power) % modulo
            j++
        }
        if j >= k && hash == hashValue {
            ansIdx = i
        }
    }
    return s[ansIdx : ansIdx+k]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length();
        long hash = 0, p = 1;
        int ansIdx = -1;
        for (int i = n - 1, j = 0; i >= 0; --i) {
            hash = (hash * power + (s.charAt(i) - 'a' + 1)) % modulo;
            if (j >= k) {
                hash = (hash - (p * (s.charAt(i + k) - 'a' + 1)) % modulo + modulo) % modulo;
            } else {
                p = (p * power) % modulo;
                ++j;
            }
            if (j >= k && hash == hashValue) ansIdx = i;
        }
        return s.substring(ansIdx, ansIdx + k);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun subStrHash(s: String, power: Int, modulo: Int, k: Int, hashValue: Int): String {
        val n = s.length
        var hash = 0L
        var p = 1L
        var ansIdx = -1
        var j = 0
        for (i in n - 1 downTo 0) {
            hash = (hash * power + (s[i] - 'a' + 1)) % modulo
            if (j >= k) {
                hash = (hash - (p * (s[i + k] - 'a' + 1)) % modulo + modulo) % modulo
            } else {
                p = (p * power) % modulo
                j++
            }
            if (j >= k && hash == hashValue) ansIdx = i
        }
        return s.substring(ansIdx, ansIdx + k)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def subStrHash(self, s: str, power: int, modulo: int, k: int, hashValue: int) -> str:
        n = len(s)
        hash = 0
        p = 1
        ans_idx = -1
        j = 0
        for i in range(n - 1, -1, -1):
            hash = (hash * power + (ord(s[i]) - ord('a') + 1)) % modulo
            if j >= k:
                hash = (hash - (p * (ord(s[i + k]) - ord('a') + 1)) % modulo + modulo) % modulo
            else:
                p = (p * power) % modulo
                j += 1
            if j >= k and hash == hashValue:
                ans_idx = i
        return s[ans_idx:ans_idx + k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn sub_str_hash(s: String, power: i32, modulo: i32, k: i32, hash_value: i32) -> String {
        let s = s.as_bytes();
        let n = s.len();
        let (mut hash, mut p, mut ans_idx, mut j) = (0i64, 1i64, None, 0);
        for i in (0..n).rev() {
            hash = (hash * power as i64 + (s[i] - b'a' + 1) as i64) % modulo as i64;
            if j >= k {
                hash = (hash - (p * (s[i + k as usize] - b'a' + 1) as i64) % modulo as i64 + modulo as i64) % modulo as i64;
            } else {
                p = (p * power as i64) % modulo as i64;
                j += 1;
            }
            if j >= k && hash == hash_value as i64 {
                ans_idx = Some(i);
            }
        }
        let idx = ans_idx.unwrap();
        String::from_utf8(s[idx..idx + k as usize].to_vec()).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    subStrHash(s: string, power: number, modulo: number, k: number, hashValue: number): string {
        const n = s.length;
        let hash = 0, p = 1, ansIdx = -1, j = 0;
        for (let i = n - 1; i >= 0; --i) {
            hash = (hash * power + (s.charCodeAt(i) - 96)) % modulo;
            if (j >= k) {
                hash = (hash - (p * (s.charCodeAt(i + k) - 96)) % modulo + modulo) % modulo;
            } else {
                p = (p * power) % modulo;
                j++;
            }
            if (j >= k && hash === hashValue) ansIdx = i;
        }
        return s.substring(ansIdx, ansIdx + k);
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we process each character once and update the hash in constant time.
  • 🧺 Space complexity: O(1), as only a few variables are used regardless of input size.