Find the occurrence of first almost equal substring

String String Matching

15.3% acceptance

Feb 23, 2026

You are given two strings s and pattern. A string x is called almost equal to y if you can change at most one character in x to make it identical to y. Return the smallest starting index of a substring in s that is almost equal to pattern. If no such index exists, return -1. A substring is a contiguous non-empty sequence of characters within a string.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_starting_index(s: String, pattern: String) -> i32 {
    let s = s.as_bytes();
    let p = pattern.as_bytes();
    let n = s.len();
    let m = p.len();

    // Z-function for prefix matching (s vs p)
    // z_forward[i] = length of longest prefix of p that matches p[i..]
    fn z_function(t: &[u8]) -> Vec<usize> {
      let n = t.len();
      let mut z = vec![0usize; n];
      z[0] = n;
      let (mut l, mut r) = (0, 0);
      for i in 1..n {
        if i < r { z[i] = (r - i).min(z[i - l]); }
        while i + z[i] < n && t[z[i]] == t[i + z[i]] { z[i] += 1; }
        if i + z[i] > r { l = i; r = i + z[i]; }
      }
      z
    }

    // prefix_match[i] = length of longest prefix of p matching s[i..]
    let combined_forward: Vec<u8> = p.iter().chain(std::iter::once(&b'#')).chain(s.iter()).cloned().collect();
    let zf = z_function(&combined_forward);
    // prefix_match[i] = min(zf[m+1+i], m) for i in 0..n
    let prefix_match: Vec<usize> = (0..n).map(|i| zf[m + 1 + i].min(m)).collect();

    // suffix_match[i] = length of longest suffix of p matching s[..=i] from right
    // Reverse both and compute Z
    let p_rev: Vec<u8> = p.iter().cloned().rev().collect();
    let s_rev: Vec<u8> = s.iter().cloned().rev().collect();
    let combined_rev: Vec<u8> = p_rev.iter().chain(std::iter::once(&b'#')).chain(s_rev.iter()).cloned().collect();
    let zr = z_function(&combined_rev);
    // suffix_match[i] = zr[m+1+(n-1-i)] = how many chars from end of p match s ending at i
    let suffix_match: Vec<usize> = (0..n).map(|i| zr[m + 1 + (n - 1 - i)].min(m)).collect();

    for start in 0..=(n - m) {
      let pm = prefix_match[start];
      if pm == m { return start as i32; } // exact match
      // One mismatch at position pm, need suffix from pm+1 to end to match
      let end = start + m - 1;
      let sm = suffix_match[end];
      if pm + sm >= m - 1 {
        return start as i32;
      }
    }
    -1
  }
}