Subsequence With the Minimum Score

Problem

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 maket _ 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 "_a_ b _c_ d _e_ " while "aec" is not).

Examples

Example 1

Input: s = "abacaba", t = "bzaa"
Output: 1
Explanation: In this example, we remove the character "z" at index 1 (0-indexed).
The string t becomes "baa" which is a subsequence of the string "abacaba" and the score is 1 - 1 + 1 = 1.
It can be proven that 1 is the minimum score that we can achieve.

Example 2

Input: s = "cde", t = "xyz"
Output: 3
Explanation: In this example, we remove characters "x", "y" and "z" at indices 0, 1, and 2 (0-indexed).
The string t becomes "" which is a subsequence of the string "cde" and the score is 2 - 0 + 1 = 3.
It can be proven that 3 is the minimum score that we can achieve.

Constraints

• 1 <= s.length, t.length <= 10^5
• s and t consist of only lowercase English letters.

Solution

Method 1 - Prefix/Suffix Positions + Binary Search

Intuition

Precompute where each prefix of t can be matched in s (left-most positions) and where each suffix of t can be matched in s (right-most positions). Deleting a contiguous block t[l..r] is possible iff the prefix t[0..l-1] appears in s strictly before the suffix t[r+1..m-1]. Using the two position arrays we can binary-search the minimal suffix start that stays after a given prefix match.

Approach

1. Let m = len(t). Build left[0..m-1] where left[i] is the smallest index in s where t[0..i] is a subsequence (or INF if impossible).
2. Build right[0..m-1] where right[i] is the largest index in s where t[i..m-1] is a subsequence (or -INF if impossible).
3. Extend right with right[m] = +INF and left with a virtual left[-1] = -1 to simplify boundaries.
4. For each l from 0..m (delete starting at l), binary-search the smallest k >= l such that right[k] > left[l-1]. Then the deleted length is k - l. Track the minimum.
5. Edge cases: if t is already a subsequence of s then answer is 0; if no part can be matched then answer is m.

Code

C++

class Solution {
 public:
  int minimumScore(string s, string t) {
    int n = s.size(), m = t.size();
    const int INF = 1e9;
    vector<int> left(m, INF), right(m, -INF);
    // build left
    int p = 0;
    for (int i = 0; i < n && p < m; ++i) if (s[i] == t[p]) left[p++] = i;
    for (int i = 1; i < m; ++i) if (left[i] == INF) left[i] = left[i-1] == INF ? INF : left[i];
    // build right
    p = m - 1;
    for (int i = n-1; i >= 0 && p >= 0; --i) if (s[i] == t[p]) right[p--] = i;

    // prepare R array of size m+1 where R[m] = INF
    vector<int> R(m+1);
    for (int i = 0; i < m; ++i) R[i] = right[i];
    R[m] = INF;

    int ans = m;
    // Lprev: left index for prefix length l-1; for l=0 use -1
    for (int l = 0; l <= m; ++l) {
      int left_idx = (l == 0) ? -1 : left[l-1];
      // binary search smallest k in [l..m] with R[k] > left_idx
      int lo = l, hi = m, pos = m+1;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (R[mid] > left_idx) { pos = mid; hi = mid - 1; }
        else lo = mid + 1;
      }
      if (pos <= m) ans = min(ans, pos - l);
    }
    return ans;
  }
};

Go

func MinimumScore(s string, t string) int {
  n, m := len(s), len(t)
  INF := int(1e9)
  left := make([]int, m)
  for i := range left { left[i] = INF }
  right := make([]int, m)
  for i := range right { right[i] = -INF }

  p := 0
  for i := 0; i < n && p < m; i++ { if s[i] == t[p] { left[p] = i; p++ } }
  p = m-1
  for i := n-1; i >= 0 && p >= 0; i-- { if s[i] == t[p] { right[p] = i; p-- } }

  R := make([]int, m+1)
  for i := 0; i < m; i++ { R[i] = right[i] }
  R[m] = INF

  ans := m
  for l := 0; l <= m; l++ {
    leftIdx := -1
    if l > 0 { leftIdx = left[l-1] }
    // binary search
    lo, hi := l, m
    pos := m+1
    for lo <= hi {
      mid := (lo + hi) / 2
      if R[mid] > leftIdx { pos = mid; hi = mid - 1 } else { lo = mid + 1 }
    }
    if pos <= m && pos-l < ans { ans = pos - l }
  }
  return ans
}

Java

class Solution {
  public int minimumScore(String s, String t) {
    int n = s.length(), m = t.length();
    final int INF = 1_000_000_000;
    int[] left = new int[m]; Arrays.fill(left, INF);
    int[] right = new int[m]; Arrays.fill(right, -INF);

    int p = 0;
    for (int i = 0; i < n && p < m; ++i) if (s.charAt(i) == t.charAt(p)) left[p++] = i;
    p = m - 1;
    for (int i = n-1; i >= 0 && p >= 0; --i) if (s.charAt(i) == t.charAt(p)) right[p--] = i;

    int[] R = new int[m+1];
    for (int i = 0; i < m; ++i) R[i] = right[i];
    R[m] = INF;

    int ans = m;
    for (int l = 0; l <= m; ++l) {
      int leftIdx = (l == 0) ? -1 : left[l-1];
      int lo = l, hi = m, pos = m+1;
      while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (R[mid] > leftIdx) { pos = mid; hi = mid - 1; }
        else lo = mid + 1;
      }
      if (pos <= m) ans = Math.min(ans, pos - l);
    }
    return ans;
  }
}

Kotlin

class Solution {
  fun minimumScore(s: String, t: String): Int {
    val n = s.length; val m = t.length
    val INF = 1_000_000_000
    val left = IntArray(m) { INF }
    val right = IntArray(m) { -INF }
    var p = 0
    for (i in 0 until n) if (p < m && s[i] == t[p]) left[p++] = i
    p = m - 1
    for (i in n-1 downTo 0) if (p >= 0 && s[i] == t[p]) right[p--] = i

    val R = IntArray(m+1)
    for (i in 0 until m) R[i] = right[i]
    R[m] = INF

    var ans = m
    for (l in 0..m) {
      val leftIdx = if (l == 0) -1 else left[l-1]
      var lo = l; var hi = m; var pos = m+1
      while (lo <= hi) {
        val mid = (lo + hi) ushr 1
        if (R[mid] > leftIdx) { pos = mid; hi = mid - 1 } else lo = mid + 1
      }
      if (pos <= m) ans = minOf(ans, pos - l)
    }
    return ans
  }
}

Python

class Solution:
  def minimumScore(self, s: str, t: str) -> int:
    n, m = len(s), len(t)
    INF = 10**9
    left = [INF] * m
    right = [-INF] * m

    p = 0
    for i, ch in enumerate(s):
      if p < m and ch == t[p]:
        left[p] = i
        p += 1

    p = m - 1
    for i in range(n-1, -1, -1):
      if p >= 0 and s[i] == t[p]:
        right[p] = i
        p -= 1

    R = right + [INF]
    ans = m
    # helper binary search over R
    def bs(lo: int, hi: int, target: int) -> int:
      pos = hi + 1
      while lo <= hi:
        mid = (lo + hi) // 2
        if R[mid] > target:
          pos = mid
          hi = mid - 1
        else:
          lo = mid + 1
      return pos

    for l in range(0, m+1):
      left_idx = -1 if l == 0 else left[l-1]
      k = bs(l, m, left_idx)
      if k <= m:
        ans = min(ans, k - l)
    return ans

Rust

impl Solution {
  pub fn minimum_score(s: String, t: String) -> i32 {
    let n = s.len(); let m = t.len();
    let s: Vec<char> = s.chars().collect();
    let t: Vec<char> = t.chars().collect();
    let inf = 1_000_000_000i32;
    let mut left = vec![inf; m];
    let mut right = vec![-inf; m];
    let mut p = 0usize;
    for i in 0..n {
      if p < m && s[i] == t[p] { left[p] = i as i32; p += 1 }
    }
    if m == 0 { return 0 }
    p = m - 1;
    for i in (0..n).rev() {
      if p < m && s[i] == t[p] { right[p] = i as i32; if p==0 { break } else { p -= 1 } }
    }
    let mut R: Vec<i32> = right.clone(); R.push(inf);
    let mut ans = m as i32;
    for l in 0..=m {
      let left_idx = if l==0 { -1 } else { left[l-1] };
      // binary search
      let mut lo = l; let mut hi = m; let mut pos = (m+1) as usize;
      while lo <= hi {
        let mid = (lo + hi) / 2;
        if R[mid] > left_idx { pos = mid; if mid==0 { break } else { hi = mid - 1 } } else { lo = mid + 1 }
      }
      if pos <= m { ans = ans.min((pos - l) as i32) }
    }
    ans
  }
}

TypeScript

function minimumScore(s: string, t: string): number {
  const n = s.length, m = t.length;
  const INF = 1e9;
  const left = new Array<number>(m).fill(INF);
  const right = new Array<number>(m).fill(-INF);
  let p = 0;
  for (let i = 0; i < n && p < m; ++i) if (s[i] === t[p]) { left[p++] = i }
  p = m - 1;
  for (let i = n-1; i >= 0 && p >= 0; --i) if (s[i] === t[p]) { right[p--] = i }
  const R = right.concat([INF]);
  let ans = m;
  function bs(lo: number, hi: number, target: number): number {
    let pos = hi + 1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (R[mid] > target) { pos = mid; hi = mid - 1 } else lo = mid + 1;
    }
    return pos;
  }
  for (let l = 0; l <= m; ++l) {
    const leftIdx = (l == 0) ? -1 : left[l-1];
    const k = bs(l, m, leftIdx);
    if (k <= m) ans = Math.min(ans, k - l);
  }
  return ans;
}

Complexity

• ⏰ Time complexity: O(n + m log m) — building the left/right arrays costs O(n + m) and binary-searching for each prefix adds O(m log m) in the worst case.
• 🧺 Space complexity: O(m) — we store the two position arrays of length m.

Method 2 - Two-pointer linear sweep (O(n + m))

Intuition

Instead of binary-searching each prefix, walk the string s once to record earliest matches for prefixes and latest matches for suffixes, then use two pointers on the right array to find valid suffix starts for increasing prefixes in linear time.

Approach

1. Compute left and right as in Method 1.
2. Use a pointer k running over 0..m for suffix start; maintain that right[k] is the earliest suffix position greater than the current left_idx.
3. Slide l from 0..m and advance k while k <= m and right[k] <= left_idx.
4. For each l the deletion length is k - l. Track the minimum.

Code

Java

class Solution {
  public int minimumScore(String s, String t) {
    int n = s.length(), m = t.length();
    final int INF = 1_000_000_000;
    int[] left = new int[m]; Arrays.fill(left, INF);
    int[] right = new int[m]; Arrays.fill(right, -INF);
    int p = 0;
    for (int i = 0; i < n && p < m; ++i) if (s.charAt(i) == t.charAt(p)) left[p++] = i;
    p = m-1;
    for (int i = n-1; i >= 0 && p >= 0; --i) if (s.charAt(i) == t.charAt(p)) right[p--] = i;
    int[] R = new int[m+1]; System.arraycopy(right, 0, R, 0, m); R[m] = INF;
    int ans = m; int k = 0;
    for (int l = 0; l <= m; ++l) {
      int leftIdx = (l == 0) ? -1 : left[l-1];
      while (k <= m && R[k] <= leftIdx) ++k;
      if (k <= m) ans = Math.min(ans, k - l);
    }
    return ans;
  }
}

Python

class Solution:
  def minimumScore(self, s: str, t: str) -> int:
    n, m = len(s), len(t)
    INF = 10**9
    left = [INF] * m
    right = [-INF] * m
    p = 0
    for i, ch in enumerate(s):
      if p < m and ch == t[p]:
        left[p] = i; p += 1
    p = m - 1
    for i in range(n-1, -1, -1):
      if p >= 0 and s[i] == t[p]:
        right[p] = i; p -= 1
    R = right + [INF]
    ans = m
    k = 0
    for l in range(0, m+1):
      left_idx = -1 if l == 0 else left[l-1]
      while k <= m and R[k] <= left_idx:
        k += 1
      if k <= m:
        ans = min(ans, k - l)
    return ans

Complexity

• ⏰ Time complexity: O(n + m) — single passes over s and linear two-pointer scan.
• 🧺 Space complexity: O(m) — store the left/right arrays.