Shortest matching substring

Two Pointers String Binary Search String Matching

23.8% acceptance

Feb 25, 2026

You are given a string s and a pattern string p, where p contains exactly two '*' characters. The '*' in p matches any sequence of zero or more characters. Return the length of the shortest substring in s that matches p. If there is no such substring, return -1. Note: The empty substring is considered valid.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_matching_substring(s: String, p: String) -> i32 {
    let sb = s.as_bytes(); let n = s.len();
    // Split p at the two '*': prefix, middle, suffix
    let star_pos: Vec<usize> = p.bytes().enumerate().filter(|&(_,c)| c==b'*').map(|(i,_)| i).collect();
    let (s1, s2, _s3) = (star_pos[0], star_pos[1], p.len());
    let prefix = &p[..s1]; let middle = &p[s1+1..s2]; let suffix = &p[s2+1..];
    // KMP match: find all starting positions of prefix in s
    // Then for each prefix match, find next middle match, then suffix match
    // Returns length of shortest matching substring or -1
    fn kmp_all(text: &[u8], pat: &str) -> Vec<usize> {
      if pat.is_empty() { return (0..=text.len()).collect(); }
      let pb = pat.as_bytes(); let m = pb.len();
      let mut fail = vec![0usize; m];
      let mut j = 0;
      for i in 1..m { while j>0 && pb[i]!=pb[j] { j=fail[j-1]; } if pb[i]==pb[j] { j+=1; } fail[i]=j; }
      let mut res = Vec::new(); j=0;
      for i in 0..text.len() {
        while j>0 && text[i]!=pb[j] { j=fail[j-1]; }
        if text[i]==pb[j] { j+=1; }
        if j==m { res.push(i+1-m); j=fail[j-1]; }
      }
      res
    }
    // prefix matches: positions where prefix ends at pos (start = pos - prefix.len())
    let pre_pos = kmp_all(sb, prefix); // start positions
    // For suffix: find all end positions where suffix ends
    let suf_starts = kmp_all(sb, suffix); // start positions of suffix
    // Precompute for suffix: next_suf[i] = smallest start pos of suffix >= i
    let mut next_suf = vec![n + 1; n + 2];
    for &ss in suf_starts.iter().rev() { next_suf[ss] = ss; }
    for i in (0..n+1).rev() { if next_suf[i] > next_suf.get(i+1).copied().unwrap_or(n+1) { next_suf[i] = next_suf[i+1]; } }
    let mid_pos = kmp_all(sb, middle);
    // For middle: next_mid[i] = smallest start pos of middle >= i
    let mut next_mid = vec![n + 1; n + 2];
    for &ms in mid_pos.iter().rev() { next_mid[ms] = ms; }
    for i in (0..n+1).rev() { if next_mid[i] > next_mid.get(i+1).copied().unwrap_or(n+1) { next_mid[i] = next_mid[i+1]; } }
    let mut ans = i32::MAX;
    for &pp in &pre_pos {
      let pre_end = pp + prefix.len(); // exclusive
      // Find middle start >= pre_end
      let ms = next_mid[pre_end.min(n+1)];
      if ms > n { continue; }
      let mid_end = ms + middle.len();
      // Find suffix start >= mid_end
      let ss = next_suf[mid_end.min(n+1)];
      if ss > n { continue; }
      let sub_end = ss + suffix.len();
      let len = (sub_end - pp) as i32;
      if len < ans { ans = len; }
    }
    if ans == i32::MAX { -1 } else { ans }
  }
}