Find substring with given hash value

String Sliding Window Rolling Hash Hash Function

26.0% acceptance

Feb 25, 2026

447

385

The hash of a 0-indexed string s of length k, given integers p and m, is computed as: hash(s, p, m) = (val(s[0]) * p^0 + val(s[1]) * p^1 + ... + val(s[k-1]) * p^(k-1)) mod m Where val(s[i]) = index of s[i] in alphabet (val('a') = 1 to val('z') = 26). Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn sub_str_hash(
    s: String,
    power: i32,
    modulo: i32,
    k: i32,
    hash_value: i32,
  ) -> String {
    let p = power as i64;
    let m = modulo as i64;
    let hv = hash_value as i64;
    let k = k as usize;
    let bytes = s.as_bytes();
    let n = bytes.len();

    // p^(k-1) mod m
    let pk = (0..k - 1).fold(1i64, |acc, _| acc * p % m);

    // Compute hash for last window s[n-k..n] from right approach
    // h[i] = val(s[i]) + p*val(s[i+1]) + ... + p^(k-1)*val(s[i+k-1])
    // Slide left: h[i-1] = val(s[i-1]) + p*(h[i] - p^(k-1)*val(s[i+k-1]))
    let val = |idx: usize| -> i64 { (bytes[idx] - b'a' + 1) as i64 };

    let mut cur_hash = 0i64;
    let mut pw = 1i64;
    for j in 0..k {
      cur_hash = (cur_hash + val(n - k + j) * pw) % m;
      pw = pw * p % m;
    }

    let mut result_idx = n; // will be set
    if cur_hash == hv {
      result_idx = n - k;
    }

    for i in (0..n - k).rev() {
      // Remove s[i+k] contribution (it has power p^(k-1)) and add s[i] at power 0
      let remove = val(i + k) * pk % m;
      cur_hash = (val(i) + p * ((cur_hash - remove + m) % m)) % m;
      if cur_hash == hv {
        result_idx = i;
      }
    }

    s[result_idx..result_idx + k].to_string()
  }
}