最少得分子序列

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.

/*
 * 思路：
 * 1. 使用Java Stream API来处理前缀和后缀匹配。
 * 2. 我们需要在字符串 t 中删除字符，使得 t 成为 s 的子序列。
 * 3. 使用双指针的方法，一个从 t 的开头向后遍历，另一个从 t 的结尾向前遍历，来确定删除区间。
 */

import java.util.stream.IntStream;

public class Solution {
    public int minScore(String s, String t) {
        int n = s.length(), m = t.length();
        int[] prefix = new int[m + 1];
        int[] suffix = new int[m + 1];
        
        IntStream.range(0, m).forEach(i -> {
            if (i < n && t.charAt(i) == s.charAt(i)) {
                prefix[i + 1] = prefix[i] + 1;
            } else {
                prefix[i + 1] = prefix[i];
            }
        });
        
        IntStream.range(0, m).forEach(i -> {
            if (i < n && t.charAt(m - 1 - i) == s.charAt(n - 1 - i)) {
                suffix[i + 1] = suffix[i] + 1;
            } else {
                suffix[i + 1] = suffix[i];
            }
        });
        
        return IntStream.rangeClosed(0, m)
                .filter(i -> prefix[i] + suffix[m - i] >= n)
                .map(i -> Math.max(0, m - n))
                .min().orElse(Integer.MAX_VALUE);
    }
}

该题解采用了一种双指针和后缀数组的混合策略，来确定最小得分。首先，从后向前遍历字符串s，同时使用指针j跟踪字符串t，寻找t作为s的子序列的最后一个字符的位置。这个位置存储在suf数组中，suf[i]表示s从i开始，t需要删除到哪个位置才能成为s的子序列。然后，从前向后遍历字符串s，同时更新指针j来检查s的每个字符是否与t的当前字符匹配，如果匹配，则移动j。对于每个匹配，计算得分suf[i + 1] - j，这是当前i的最小得分。最后，返回所有可能得分中的最小值。

O(n)

O(n)