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).

class Solution {
public:
    int minimumScore(string s, string t) {
        int n = s.length(), m = t.length();
        vector<int> lmatch(m,INT_MAX);
        for(int i = 0, j = 0; i < n and j < m; i++) {
            if(s[i] == t[j]) {
                lmatch[j] = i;
                j += 1;
            }
        }
        int p = m - 1;
        while(p >= 0 and lmatch[p] == INT_MAX) p -= 1;
        int res = m - (p + 1);
        for(int i = n - 1, j = m - 1; i >= 0 and j >= 0; i--) {
            if(s[i] == t[j]) {
                p = min(p,j);
                while(p >= 0 and lmatch[p] >= i) p -= 1;
                res = min(res, (j - 1) - (p + 1) + 1);
                j -= 1;
            }
        }
        return max(0,res);
    }
};