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 of the string is 0 if no characters are removed from the string t, otherwise:
- Let
leftbe the minimum index among all removed characters. - Let
rightbe 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. For example, "ace" is a subsequence of "abcde" while "aec" is not.
Example 1
Input
s = "abacaba", t = "bzaa"Output
1Removing the character "z" at index 1 makes
t become "baa", which is a subsequence of "abacaba", and the score is 1.Example 2
Input
s = "cde", t = "xyz"Output
3Removing all characters "x", "y", and "z" makes
t become an empty string, which is a subsequence of "cde", and the score is 3.Constraints
- 1 <= s.length, t.length <= 10^5
- s and t consist of only lowercase English letters.