LeetCode in Kotlin
2565. Subsequence With the Minimum Score
Hard
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 ta 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 <= 105sandtconsist of only lowercase English letters.
Solution
class Solution {
fun minimumScore(s: String, t: String): Int {
val m = s.length
val n = t.length
val left = IntArray(m)
run {
var i = 0
var j = 0
while (i < m) {
if (j < n && s[i] == t[j]) {
++j
}
left[i] = j
i++
}
}
val right = IntArray(m)
run {
var i = m - 1
var j = n - 1
while (i >= 0) {
if (j >= 0 && s[i] == t[j]) {
--j
}
right[i] = j
i--
}
}
var min = (n - left[m - 1]).coerceAtMost(right[0] + 1)
var i = 0
while (i + 1 < m) {
min = min.coerceAtMost(0.coerceAtLeast(right[i + 1] - left[i] + 1))
i++
}
return min
}
}