Leetcode 2565: Subsequence With the Minimum Score

You are given two strings s and t.

You are allowed to remove any number of characters from the string t.

The score 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.

Problem Analysis:

To find minimum possible score also means to find the maximum sum that of matched prefix substring and matched suffix substring length.

So we can use greedy algorithm. we scan suf_index in string s that stores every suffix substring of string t, and scan pre_index in string s that stores every prefix substring of string t. Then the minimum distance of valid pre_index and suf_index pair is the answer.

Solution

class Solution {
public:
    int minimumScore(string s, string t) {
        vector<int> dp(t.size(), -1);
        int k{(int)t.size() - 1};
        for (int i = s.size() - 1; k >= 0 && i >= 0; --i) {
            if (s[i] == t[k]) dp[k--] = i;
        }
        
        int res{k + 1};
        for (int i = 0, j = 0; i < s.size() && j < t.size() && res > 0; ++i) {
            if (s[i] == t[j]) {
                for (; k < t.size() && dp[k] <= i; ++k);
                res = min(res, k - (++j));
            }
        }
        
        return res;
    }
};

time complexity is O(max(s.size(), t.size()))

Space complexity is O(t.size())