#2565
Subsequence With the Minimum Score
master · 1890 · lc hard +32 · verified · 33.2% accepted · 406 likes · top 11%
Description
Given strings s and t, you may delete any set of characters from t. If deletions are made, the score equals right - left + 1 where left and right are the minimum and maximum removed indices; if nothing is removed the score is 0. Return the minimum score needed to make t a subsequence of s.
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.
Code
1
2
3