题目描述：
给你两个字符串 s 和 t 。
你可以从字符串 t 中删除任意数目的字符。
如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：
- 令
left 为删除字符中的最小下标。 - 令
right 为删除字符中的最大下标。
字符串的得分为 right - left + 1 。
请你返回使 t 成为 s 子序列的最小得分。
一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。
数据范围：
$1\le s.len, t.len \le 10^5$
题解：
首先，如果删除的下标边界是 $l, r$ ，那么可以贪心的删除中间所有的字符。这样的话就是需要删除最短的子串，也就是保留最长的前缀和最长的后缀。可以预处理出来 $s[:i]$ 可以匹配多长的前缀，以及 $s[i:]$ 可以匹配多长的后缀。
然后直接贪心的选最长的前缀和后缀就行，注意特殊情况。有的可能没有前缀了，有的可能没有后缀了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minimumScore(string s, string t)
{
int n = s.length(), m = t.length();
int i = 0, j = 0;
vector<int> pre(n);
while (i < n)
{
pre[i] = (i == 0 ? 0 : pre[i - 1]);
if (j < m && s[i] == t[j])
{
pre[i] = j + 1;
++j;
}
++i;
}
vector<int> suf(n + 1);
i = n - 1, j = m - 1;
while (i >= 0)
{
suf[i] = (i == n - 1 ? 0 : suf[i + 1]);
if (j >= 0 && s[i] == t[j])
{
suf[i] = m - j;
--j;
}
--i;
}
int ans = INF;
ans = min(ans, m - pre[n - 1]);
ans = min(ans, m - suf[0]);
if (ans == 0)
return ans;
for (int i = 0; i < n; ++i)
{
if (pre[i] + suf[i + 1] >= m)
return 0;
ans = min(ans, m - pre[i] - suf[i + 1]);
}
return ans;
}
};
|