2565. Subsequence With the Minimum Score

Description

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.

Solutions

Solution 1: Prefix and Suffix Preprocessing + Binary Search

According to the problem, we know that the range of the index to delete characters is [left, right]. The optimal approach is to delete all characters within the range [left, right]. In other words, we need to delete a substring from string \(t\), so that the remaining prefix of string \(t\) can match the prefix of string \(s\), and the remaining suffix of string \(t\) can match the suffix of string \(s\), and the prefix and suffix of string \(s\) do not overlap. Note that the match here refers to subsequence matching.

Therefore, we can preprocess to get arrays \(f\) and \(g\), where \(f[i]\) represents the minimum number of characters in the prefix \(t[0,..i]\) of string \(t\) that match the first \([0,..f[i]]\) characters of string \(s\); similarly, \(g[i]\) represents the maximum number of characters in the suffix \(t[i,..n-1]\) of string \(t\) that match the last \([g[i],..n-1]\) characters of string \(s\).

The length of the deleted characters has monotonicity. If the condition is satisfied after deleting a string of length \(x\), then the condition is definitely satisfied after deleting a string of length \(x+1\). Therefore, we can use the method of binary search to find the smallest length that satisfies the condition.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of string \(t\).

Python3JavaC++Go

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)

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;
    }
}

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;
    }
};

func minimumScore(s string, t string) int {
    m, n := len(s), len(t)
    f := make([]int, n)
    g := make([]int, n)
    for i := range f {
        f[i] = 1 << 30
        g[i] = -1
    }
    for i, j := 0, 0; i < m && j < n; i++ {
        if s[i] == t[j] {
            f[j] = i
            j++
        }
    }
    for i, j := m-1, n-1; i >= 0 && j >= 0; i-- {
        if s[i] == t[j] {
            g[j] = i
            j--
        }
    }
    return sort.Search(n+1, func(x int) bool {
        for k := 0; k < n; k++ {
            i, j := k-1, k+x
            l, r := -1, m+1
            if i >= 0 {
                l = f[i]
            }
            if j < n {
                r = g[j]
            }
            if l < r {
                return true
            }
        }
        return false
    })
}

Comments