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. (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.
class Solution:
def minimumScore(self, s: str, t: str) -> int:
def check(x):
for k in range(n):
i, j = k - 1, k + x
l = f[i] if i >= 0 else -1
r = g[j] if j < n else m + 1
if l < r:
return True
return False
m, n = len(s), len(t)
f = [inf] * n
g = [-1] * n
i, j = 0, 0
while i < m and j < n:
if s[i] == t[j]:
f[j] = i
j += 1
i += 1
i, j = m - 1, n - 1
while i >= 0 and j >= 0:
if s[i] == t[j]:
g[j] = i
j -= 1
i -= 1
return bisect_left(range(n + 1), True, key=check)class Solution {
private int m;
private int n;
private int[] f;
private int[] g;
public int minimumScore(String s, String t) {
m = s.length();
n = t.length();
f = new int[n];
g = new int[n];
for (int i = 0; i < n; ++i) {
f[i] = 1 << 30;
g[i] = -1;
}
for (int i = 0, j = 0; i < m && j < n; ++i) {
if (s.charAt(i) == t.charAt(j)) {
f[j] = i;
++j;
}
}
for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {
if (s.charAt(i) == t.charAt(j)) {
g[j] = i;
--j;
}
}
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
private boolean check(int len) {
for (int k = 0; k < n; ++k) {
int i = k - 1, j = k + len;
int l = i >= 0 ? f[i] : -1;
int r = j < n ? g[j] : m + 1;
if (l < r) {
return true;
}
}
return false;
}
}class Solution {
public:
int minimumScore(string s, string t) {
int m = s.size(), n = t.size();
vector<int> f(n, 1e6);
vector<int> g(n, -1);
for (int i = 0, j = 0; i < m && j < n; ++i) {
if (s[i] == t[j]) {
f[j] = i;
++j;
}
}
for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i) {
if (s[i] == t[j]) {
g[j] = i;
--j;
}
}
auto check = [&](int len) {
for (int k = 0; k < n; ++k) {
int i = k - 1, j = k + len;
int l = i >= 0 ? f[i] : -1;
int r = j < n ? g[j] : m + 1;
if (l < r) {
return true;
}
}
return false;
};
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};func minimumScore(s string, t string) int {
m, n := len(s), len(t)
f := make([]int, n)
g := make([]int, n)
for i := range f {
f[i] = 1 << 30
g[i] = -1
}
for i, j := 0, 0; i < m && j < n; i++ {
if s[i] == t[j] {
f[j] = i
j++
}
}
for i, j := m-1, n-1; i >= 0 && j >= 0; i-- {
if s[i] == t[j] {
g[j] = i
j--
}
}
return sort.Search(n+1, func(x int) bool {
for k := 0; k < n; k++ {
i, j := k-1, k+x
l, r := -1, m+1
if i >= 0 {
l = f[i]
}
if j < n {
r = g[j]
}
if l < r {
return true
}
}
return false
})
}