Problem statement

You are given two strings s and t. You may delete any number of characters from t (possibly none). Afterwards, the remaining t must be a subsequence of s (obtainable from s by deleting characters without reordering).

The score of a deletion is:

• 0 if nothing is deleted;
• otherwise right - left + 1, where left and right are the smallest and largest indices in t of the deleted characters.

Return the minimum possible score that makes t a subsequence of s.

Example 1

Input: s = "kairo", t = "kxro"
Output: 1
Explanation: Delete `x` (index 1); `kro` is a subsequence of `kairo`.

Example 2

Input: s = "code", t = "duel"
Output: 3
Explanation: Neither `u` nor `l` occurs in `s`, so both must go; deleting indices 1..3 leaves `d`.

Example 3

Input: s = "streak", t = "sea"
Output: 0
Explanation: `sea` is already a subsequence of `streak`.

Constraints

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

Hints for Subsequence With the Minimum Score

1. Hint 1

   Only left and right matter for the score, so if you delete anything you may as well delete the whole block t[left..right]. The task becomes: keep a prefix and a suffix of t and make their concatenation a subsequence of s.

2. Hint 2

   Match prefixes greedily from the left of s (as early as possible) and suffixes greedily from the right of s (as late as possible). Record, for every suffix start k, the latest index of s where matching t[k..] can begin.

3. Hint 3

   For each prefix length, the prefix ends at some position of s; the best suffix is the longest one whose recorded start lies after that position. Both move monotonically, so a two-pointer sweep finds the best block in linear time.

How to solve Subsequence With the Minimum Score

Deleting a contiguous block of t is always optimal, so the answer is the shortest block whose removal leaves prefix + suffix as a subsequence of s. Greedy matching from both ends tells, for every prefix, how far into s it reaches, and for every suffix, how late in s it can start.

Approach

1. Compute suf[k] for the suffixes t[k..]: scan s from the right, matching t from its end; suf[k] is the index in s where t[k] gets matched. Let first be the smallest k that can be matched this way (suf[m] = n for the empty suffix).
2. If first == 0, t is already a subsequence: return 0. Otherwise start with ans = first (delete the prefix t[0..first-1]).
3. Sweep the prefix: match t[0], t[1], … greedily from the left of s, with q the position just after the last matched character. Stop when a character cannot be matched.
4. After matching t[0..i], advance a pointer k (never below max(first, i + 1)) until suf[k] >= q; the block t[i+1..k-1] is deletable, so ans = min(ans, k - i - 1).
5. Return ans.

Why it works

If the deleted indices span [left, right], deleting everything in between too keeps the remainder a subsequence and does not change the score — so blocks suffice. A prefix and a suffix can be matched disjointly exactly when the earliest end of the prefix comes before the latest start of the suffix, which is what suf[k] >= q tests. Earliest-left and latest-right greedy matches are optimal for these two questions, and since q only grows and suf is increasing in k, the pointer k never has to move back.

Complexity

• Time — O(|s| + |t|)
• Space — O(|t|)

Pitfalls

• Trying every block with a fresh subsequence check is O(|t|^2 · |s|).
• The answer 0 (nothing deleted) is different from deleting one character — check whether t is already a subsequence first.
• Do not read suf[k] for k < first: those suffixes cannot be matched at all.

Reference solution

Python

def minimumScore(s: str, t: str) -> int:
    n, m = len(s), len(t)
    suf = [n] * (m + 1)
    p = n - 1
    j = m - 1
    while j >= 0:
        while p >= 0 and s[p] != t[j]:
            p -= 1
        if p < 0:
            break
        suf[j] = p
        p -= 1
        j -= 1
    first = j + 1
    if first == 0:
        return 0
    ans = first
    q = 0
    k = first
    for i in range(m):
        while q < n and s[q] != t[i]:
            q += 1
        if q == n:
            break
        q += 1
        if k <= i:
            k = i + 1
        while k < m and suf[k] < q:
            k += 1
        ans = min(ans, k - i - 1)
    return ans

Java

public static int minimumScore(String s, String t) {
    int n = s.length(), m = t.length();
    int[] suf = new int[m + 1];
    Arrays.fill(suf, n);
    int p = n - 1, j = m - 1;
    while (j >= 0) {
        while (p >= 0 && s.charAt(p) != t.charAt(j)) p--;
        if (p < 0) break;
        suf[j] = p;
        p--;
        j--;
    }
    int first = j + 1;
    if (first == 0) return 0;
    int ans = first, q = 0, k = first;
    for (int i = 0; i < m; i++) {
        while (q < n && s.charAt(q) != t.charAt(i)) q++;
        if (q == n) break;
        q++;
        if (k <= i) k = i + 1;
        while (k < m && suf[k] < q) k++;
        ans = Math.min(ans, k - i - 1);
    }
    return ans;
}

C++

int minimumScore(string s, string t) {
    int n = s.size(), m = t.size();
    vector<int> suf(m + 1, n);
    int p = n - 1, j = m - 1;
    while (j >= 0) {
        while (p >= 0 && s[p] != t[j]) p--;
        if (p < 0) break;
        suf[j] = p;
        p--;
        j--;
    }
    int first = j + 1;
    if (first == 0) return 0;
    int ans = first, q = 0, k = first;
    for (int i = 0; i < m; i++) {
        while (q < n && s[q] != t[i]) q++;
        if (q == n) break;
        q++;
        if (k <= i) k = i + 1;
        while (k < m && suf[k] < q) k++;
        ans = min(ans, k - i - 1);
    }
    return ans;
}

JavaScript

var minimumScore = function(s, t) {
    var n = s.length, m = t.length;
    var suf = new Array(m + 1).fill(n);
    var p = n - 1, j = m - 1;
    while (j >= 0) {
        while (p >= 0 && s[p] !== t[j]) p--;
        if (p < 0) break;
        suf[j] = p;
        p--;
        j--;
    }
    var first = j + 1;
    if (first === 0) return 0;
    var ans = first, q = 0, k = first;
    for (var i = 0; i < m; i++) {
        while (q < n && s[q] !== t[i]) q++;
        if (q === n) break;
        q++;
        if (k <= i) k = i + 1;
        while (k < m && suf[k] < q) k++;
        ans = Math.min(ans, k - i - 1);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard