Subsequence with the minimum score

Two Pointers String Binary Search

33.2% acceptance

Feb 25, 2026

405

You are given two strings s and t. You are allowed to remove any number of characters from the string t. The score of the string is 0 if no characters are removed from the string t, otherwise: Let left be the minimum index among all removed characters. Let right be the maximum index among all removed characters. Then the score of the string is right - left + 1. Return the minimum possible score to make t a subsequence of s. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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

    // pre[i] = minimum s-position right after matching t[0..i) greedily from left
    // Invalid = n + 1 (can't match)
    let mut pre = vec![n + 1; m + 1];
    pre[0] = 0;
    for i in 0..m {
      let start = pre[i];
      if start > n { break; }
      let mut p = start;
      while p < n && s[p] != t[i] { p += 1; }
      if p < n { pre[i + 1] = p + 1; }
    }

    // suf[j] = s-position (0-indexed) where t[j..m) starts when matched from right
    // Invalid = n + 1, suf[m] = n (empty suffix)
    let mut suf = vec![n + 1usize; m + 1];
    suf[m] = n;
    {
      let mut p = n;
      for j in (0..m).rev() {
        while p > 0 && s[p - 1] != t[j] { p -= 1; }
        if p > 0 {
          p -= 1;
          suf[j] = p;
        } else {
          break;
        }
      }
    }

    // Two-pointer: find minimum k - l where suf[k] >= pre[l]
    let mut ans = m as i32;
    let mut k = 0usize;
    for l in 0..=m {
      if pre[l] > n { break; }
      if k < l { k = l; }
      while k < m {
        if suf[k] <= n && suf[k] >= pre[l] { break; }
        k += 1;
      }
      // k == m means suf[m] = n >= pre[l] (always holds since pre[l] <= n)
      ans = ans.min(k as i32 - l as i32);
      if ans == 0 { return 0; }
    }
    ans
  }
}