# Subsequence With the Minimum Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/subsequence-with-the-minimum-score)
Canonical: https://scaleengineer.com/dsa/problems/subsequence-with-the-minimum-score
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash)
---
## 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 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).

**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 <= 105`
* `s` and `t` consist of only lowercase English letters.

# Approaches
## Brute Force
The brute-force approach systematically explores every possible scenario. We can remove any contiguous subsegment of characters from `t`. The idea is to try removing every possible substring `t[i...j]`, check if the remaining parts of `t` form a subsequence of `s`, and if they do, we consider the length of the removed substring as a potential answer. We keep track of the minimum length found so far.
**Time:** O(m^2 * (n + m)), where `n` and `m` are the lengths of `s` and `t` respectively. There are `O(m^2)` pairs of `(i, j)`. For each, string concatenation takes `O(m)` and the subsequence check takes `O(n + m)`. This is prohibitively slow. · **Space:** O(m), where `m` is the length of `t`. This is for storing the `remainingT` string in each iteration.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Extremely inefficient due to the nested loops iterating through all possible substrings to remove.; The subsequence check is repeated for many overlapping subproblems.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
This method iterates through all `O(m^2)` possible contiguous subsegments of `t` to remove. For each subsegment, defined by start and end indices `i` and `j`, we form a new string by taking `t`'s prefix up to `i` and suffix from `j`. Then, we perform a subsequence check to see if this new string is a subsequence of `s`. The subsequence check itself takes time proportional to the lengths of the strings involved. The minimum length of a valid removal `(j - i)` is recorded. This process guarantees finding the minimum score but is computationally very expensive.

```java
class Solution {
    public int minimumScore(String s, String t) {
        int m = t.length();
        int n = s.length();
        int minScore = m;

        // Case: remove nothing
        if (isSubsequence(s, t)) {
            return 0;
        }

        // Iterate through all substrings t[i...j-1] to remove
        for (int i = 0; i <= m; i++) {
            for (int j = i; j <= m; j++) {
                // Removed part is t[i...j-1]
                String prefix = t.substring(0, i);
                String suffix = t.substring(j);
                String remainingT = prefix + suffix;

                if (isSubsequence(s, remainingT)) {
                    minScore = Math.min(minScore, j - i);
                }
            }
        }
        return minScore;
    }

    private boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == t.length();
    }
}
```
### Algorithm
1. Initialize `min_score` to the length of `t`, `m`. This is the score if we remove the entire string `t`.
2. Check if `t` is already a subsequence of `s`. If so, the score is 0, and we can return immediately.
3. Iterate through all possible contiguous substrings `t[i...j]` to remove. This can be done with two nested loops:
   - The outer loop for the start index `i` from `0` to `m`.
   - The inner loop for the end index `j` from `i` to `m`.
4. For each pair `(i, j)`, we are considering removing the substring `t[i...j-1]`. The length of this removal is `j - i`.
5. Construct the remaining string `t_rem` by concatenating the prefix `t[0...i-1]` and the suffix `t[j...m-1]`.
6. Check if `t_rem` is a subsequence of `s` using a helper function. This check can be done in `O(s.length() + t_rem.length())` time with a two-pointer approach.
7. If `t_rem` is a subsequence of `s`, update `min_score = min(min_score, j - i)`.
8. After checking all `(i, j)` pairs, `min_score` will hold the minimum possible score.

## Precomputation with Binary Search
A more optimized approach involves precomputation. The problem asks us to keep a prefix and a suffix of `t`. Let's say we keep prefix `t[0...i-1]` and suffix `t[j...m-1]`. For this to be a valid subsequence of `s`, the prefix must match some part of `s` that ends before the part where the suffix match begins. We can precompute the earliest possible end positions for all prefixes of `t` and the latest possible start positions for all suffixes of `t`. With this information, for each prefix, we can efficiently find the best suffix to pair it with.
**Time:** O(n + m log m). Precomputation takes `O(n+m)`. The main loop runs `m` times, with a binary search of `O(log m)` in each iteration. · **Space:** O(m) for the `prefixEnd` and `suffixStart` arrays.
**Pros:** Significantly more efficient than the brute-force approach.; The precomputation step is linear and avoids redundant calculations.
**Cons:** Slightly more complex to implement than the brute-force approach.; Not the most optimal solution, as the binary search can be replaced by a more efficient two-pointer scan.
### Explanation
We can precompute two arrays. `prefixEnd[i]` stores the minimum ending index in `s` for the prefix `t[0...i-1]`. `suffixStart[j]` stores the maximum starting index in `s` for the suffix `t[j...m-1]`. Both arrays can be filled in `O(n+m)` time.

After precomputation, we iterate through each possible prefix length `i` from `0` to `m`. For each prefix `t[0...i-1]`, we need to find the smallest `j >= i` such that `prefixEnd[i] < suffixStart[j]`. This condition ensures that the match for the prefix in `s` does not overlap with the match for the suffix. Since `suffixStart` is sorted (non-decreasing), we can use binary search to find this `j` for each `i`. The length of the removed part is `j-i`, and we minimize this value over all valid `i`.

```java
class Solution {
    public int minimumScore(String s, String t) {
        int n = s.length(), m = t.length();

        // prefixEnd[i]: min ending index in s for t's prefix of length i
        int[] prefixEnd = new int[m + 1];
        prefixEnd[0] = -1;
        int sPtr = 0;
        for (int i = 1; i <= m; i++) {
            char target = t.charAt(i - 1);
            while (sPtr < n && s.charAt(sPtr) != target) {
                sPtr++;
            }
            if (sPtr == n) {
                for (int k = i; k <= m; k++) prefixEnd[k] = n;
                break;
            }
            prefixEnd[i] = sPtr;
            sPtr++;
        }

        // suffixStart[j]: max starting index in s for t's suffix starting at j
        int[] suffixStart = new int[m + 1];
        suffixStart[m] = n;
        sPtr = n - 1;
        for (int j = m - 1; j >= 0; j--) {
            char target = t.charAt(j);
            while (sPtr >= 0 && s.charAt(sPtr) != target) {
                sPtr--;
            }
            if (sPtr < 0) {
                for (int k = j; k >= 0; k--) suffixStart[k] = -1;
                break;
            }
            suffixStart[j] = sPtr;
            sPtr--;
        }

        int minScore = m;

        // Find min score by combining prefixes and suffixes
        for (int i = 0; i <= m; i++) {
            if (prefixEnd[i] == n) { // Prefix t[0...i-1] doesn't exist in s
                minScore = Math.min(minScore, i); // Must remove at least this prefix
                break;
            }
            // Binary search for the smallest j >= i such that suffixStart[j] > prefixEnd[i]
            int low = i, high = m, j = m + 1;
            while(low <= high) {
                int mid = low + (high - low) / 2;
                if (suffixStart[mid] > prefixEnd[i]) {
                    j = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            minScore = Math.min(minScore, j - i);
        }
        return minScore;
    }
}
```
### Algorithm
1. **Precomputation:**
   - Create an array `prefixEnd` of size `m+1`. `prefixEnd[i]` will store the minimum index `k` in `s` such that `t[0...i-1]` is a subsequence of `s[0...k]`. We can compute this in `O(n+m)` time using a two-pointer approach. If a prefix is not a subsequence of `s`, we store a sentinel value (e.g., `n`).
   - Create an array `suffixStart` of size `m+1`. `suffixStart[j]` will store the maximum index `k` in `s` such that `t[j...m-1]` is a subsequence of `s[k...n-1]`. This can be computed similarly in `O(n+m)` by iterating from the ends of the strings. If a suffix is not a subsequence, we store a sentinel value (e.g., `-1`).
2. **Finding the Minimum Score:**
   - Initialize `minScore` to `m`.
   - Iterate with `i` from `0` to `m`, representing the length of the prefix `t[0...i-1]` that we keep.
   - For each `i`, if `prefixEnd[i]` is valid (not the sentinel value), we need to find the longest possible suffix `t[j...m-1]` that can follow. This means finding the smallest `j >= i`.
   - The condition for a valid combination of prefix `t[0...i-1]` and suffix `t[j...m-1]` is `prefixEnd[i] < suffixStart[j]`.
   - Since `suffixStart` is non-decreasing, for a fixed `i`, we can use binary search on the range `[i, m]` to find the smallest `j` that satisfies the condition.
   - If such a `j` is found, the score is `j - i`. We update `minScore = min(minScore, j - i)`.
   - We also need to consider the case where we only keep the prefix, which means removing `t[i...m-1]`. The score is `m-i`. This is implicitly handled if the binary search returns `j=m`.
3. Return `minScore`.

## Optimal Two-Pointer Scan
This approach optimizes the previous one by replacing the binary search with a more efficient two-pointer scan. After the same `O(n+m)` precomputation, we can find the minimum score in `O(m)` time. The key observation is that as we extend the prefix we keep (by incrementing `i`), the earliest position its match can end in `s` (`prefixEnd[i]`) is non-decreasing. Consequently, the starting position of the suffix we need (`suffixStart[j]`) must also be further along. This monotonicity allows us to use a second pointer `j` that only moves forward, avoiding the repeated logarithmic-time searches.
**Time:** O(n + m). Precomputation takes `O(n+m)`. The two-pointer scan to find the minimum score takes `O(m)` because both pointers `i` and `j` only move forward through the arrays. This gives a total linear time complexity. · **Space:** O(m) for the `prefixEnd` and `suffixStart` arrays.
**Pros:** This is the most efficient solution with optimal time complexity.; It solves the problem in a single pass after precomputation.
**Cons:** The two-pointer logic can be tricky to get right compared to the more straightforward binary search.
### Explanation
The precomputation of `prefixEnd` and `suffixStart` arrays remains the same. The improvement lies in how we find the optimal split. We use two pointers, `i` and `j`. `i` iterates from `0` to `m`, representing the length of the prefix `t[0...i-1]` to be kept. `j` points to the start of the suffix `t[j...m-1]` to be kept.

For each `i`, we need the smallest `j >= i` such that `prefixEnd[i] < suffixStart[j]`. Since `prefixEnd[i]` is non-decreasing with `i`, the valid `j` for `i+1` will be greater than or equal to the valid `j` for `i`. This allows us to use a single pass for both pointers. The `j` pointer never needs to move backward. This amortizes the search for `j` over all `i`, leading to a linear time complexity for this part of the algorithm.

```java
class Solution {
    public int minimumScore(String s, String t) {
        int n = s.length(), m = t.length();

        int[] prefixEnd = new int[m + 1];
        prefixEnd[0] = -1;
        int sPtr = 0;
        for (int i = 1; i <= m; i++) {
            char target = t.charAt(i - 1);
            while (sPtr < n && s.charAt(sPtr) != target) {
                sPtr++;
            }
            if (sPtr == n) {
                for (int k = i; k <= m; k++) prefixEnd[k] = n;
                break;
            }
            prefixEnd[i] = sPtr;
            sPtr++;
        }

        int[] suffixStart = new int[m + 1];
        suffixStart[m] = n;
        sPtr = n - 1;
        for (int j = m - 1; j >= 0; j--) {
            char target = t.charAt(j);
            while (sPtr >= 0 && s.charAt(sPtr) != target) {
                sPtr--;
            }
            if (sPtr < 0) {
                for (int k = j; k >= 0; k--) suffixStart[k] = -1;
                break;
            }
            suffixStart[j] = sPtr;
            sPtr--;
        }

        int minScore = m;
        int j = 0;
        for (int i = 0; i <= m; i++) {
            // Find smallest j >= i such that prefixEnd[i] < suffixStart[j]
            while (j <= m && (j < i || prefixEnd[i] >= suffixStart[j])) {
                j++;
            }
            if (j > m) { // No valid suffix can be appended
                 // Only option is to remove t[i...m-1]
                 minScore = Math.min(minScore, m - i);
                 break; // No longer prefixes can be formed either
            }
            minScore = Math.min(minScore, j - i);
        }
        return minScore;
    }
}
```
### Algorithm
1. **Precomputation:** This step is identical to the previous approach. We compute the `prefixEnd` and `suffixStart` arrays in `O(n+m)` time.
2. **Finding the Minimum Score with Two Pointers:**
   - Initialize `minScore` to `m`.
   - Initialize a pointer `j = 0` for the `suffixStart` array.
   - Iterate with a pointer `i` from `0` to `m` (for each prefix `t[0...i-1]`):
     - First, check if the prefix `t[0...i-1]` is valid. If `prefixEnd[i]` is the sentinel value `n`, it means this prefix (and any longer ones) cannot be formed. We can break the loop.
     - We need to find the smallest `j >= i` such that `prefixEnd[i] < suffixStart[j]`. We can use the `j` pointer for this.
     - Since `i` is increasing, `prefixEnd[i]` is non-decreasing. This means the required `j` will also be non-decreasing. So, we don't need to reset `j` for each `i`.
     - Advance the `j` pointer: `while (j <= m && (j < i || prefixEnd[i] >= suffixStart[j])) { j++; }`.
     - This loop finds the smallest `j` that is at least `i` and satisfies the condition `prefixEnd[i] < suffixStart[j]`.
     - If `j <= m`, we have a valid split. The score is `j - i`. Update `minScore = min(minScore, j - i)`.
     - If `j` goes beyond `m`, it means for the current prefix, no suffix can be appended. The only option is to remove the rest of `t`, i.e., `t[i...m-1]`. The score is `m-i`. This case is also implicitly handled by the logic.
3. Return `minScore`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[] f;
private
  int[] g;
public
  int minimumScore(String s, String t) {
    m = s.length();
    n = t.length();
    f = new int[n];
    g = new int[n];
    for (int i = 0; i < n; ++i) {
      f[i] = 1 << 30;
      g[i] = -1;
    }
    for (int i = 0, j = 0; i < m && j < n; ++i) {
      if (s.charAt(i) == t.charAt(j)) {
        f[j] = i;
        ++j;
      }
    }
    for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {
      if (s.charAt(i) == t.charAt(j)) {
        g[j] = i;
        --j;
      }
    }
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
private
  boolean check(int len) {
    for (int k = 0; k < n; ++k) {
      int i = k - 1, j = k + len;
      int l = i >= 0 ? f[i] : -1;
      int r = j < n ? g[j] : m + 1;
      if (l < r) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumScore(string s, string t) {
    int m = s.size(), n = t.size();
    vector<int> f(n, 1e6);
    vector<int> g(n, -1);
    for (int i = 0, j = 0; i < m && j < n; ++i) {
      if (s[i] == t[j]) {
        f[j] = i;
        ++j;
      }
    }
    for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {
      if (s[i] == t[j]) {
        g[j] = i;
        --j;
      }
    }
    auto check = [&](int len) {
      for (int k = 0; k < n; ++k) {
        int i = k - 1, j = k + len;
        int l = i >= 0 ? f[i] : -1;
        int r = j < n ? g[j] : m + 1;
        if (l < r) {
          return true;
        }
      }
      return false;
    };
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def minimumScore(self, s: str, t: str) -> int: def check(x): for k in range(n): i, j = k - 1, k + x l = f[i] if i >= 0 else - 1 r = g[j] if j < n else m + 1 if l < r: return True return False m, n = len(s), len(t) f = [inf] * n g = [- 1] * n i, j = 0, 0 while i < m and j < n: if s[i] == t[j]: f[j] = i j += 1 i += 1 i, j = m - 1, n - 1 while i >= 0 and j >= 0: if s[i] == t[j]: g[j] = i j -= 1 i -= 1 return bisect_left(range(n + 1), True, key=check)

```