给你两个长度相同的字符串,s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。
示例 1:
输入:s = "abcd", t = "bcdf", cost = 3
输出:3
解释:s 中的 "abc" 可以变为 "bcd"。
开销为 3,所以最大长度为 3。
示例 2:
输入:s = "abcd", t = "cdef", cost = 3
输出:1
解释:s 中的任一字符要想变成 t 中对应的字符,其开销都是 2。
因此,最大长度为 1。
示例 3:
输入:s = "abcd", t = "acde", cost = 0
输出:1
解释:你无法作出任何改动,所以最大长度为 1。
提示:
1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
给定了长度相同的 s
和 t
,那么对于每一位而言,修改的成本都是相互独立而确定的。
我们可以先预处理出修改成本的前缀和数组 sum
。
当有了前缀和数组之后,对于任意区间 [i,j]
的修改成本,便可以通过 sum[j] - sum[i - 1]
得出。
那么接下来我们只需要找出成本不超过 maxCost
的最大长度区间,这个长度区间其实就是滑动窗口长度,滑动窗口长度的范围为 [1, n]
(n 为字符串的长度)。
通过枚举来找答案可以吗?
我们可以通过数据范围大概分析一下哈,共有 n
个滑动窗口长度要枚举,复杂度为
,对于每个滑动窗口长度,需要对整个前缀和数组进行滑动检查,复杂度为
。也就是整体复杂度是
的。
数据范围是
,那么单个样本的计算量是
,计算机单秒肯定算不完,会超时 ~
PS. 如果你对此分析方法比较陌生,可以去瞧一眼 4. 寻找两个正序数组的中位数(困难) 的总结部分 ~
因此我们直接放弃通过枚举的朴素做法。
那么如何优化呢?其实有了对于朴素解法的分析之后,无非就是两个优化方向:
:减少需要枚举的滑动窗口长度
:实现不完全滑动前缀和数组,也能确定滑动窗口长度是否合法
事实上第 2 点是无法实现的,我们只能「减少需要枚举的滑动窗口长度」。
一个
的操作往下优化,通常就是优化成
,
基本上我们可以先猜一个「二分」查找。
然后我们再来分析是否可以二分:假设我们有满足要求的长度 ans
,那么在以 ans
为分割点的数轴上(数轴的范围是滑动窗口长度的范围:[1, n]
):
<= ans
的点的修改成本必然满足 <= maxCost
> ans
的点的修改成本必然满足 > maxCost
(否则 ans
就不会是答案)因此 ans
在数轴 [1, n]
上具有二段性,我们可以使用「二分」找 ans
。得证「二分」的合理性。
PS. 三叶一直强调二分的本质是二段性,而非单调性。33. 搜索旋转排序数组(中等) 是一个很好的例子
class Solution {
public int equalSubstring(String ss, String tt, int max) {
int n = ss.length();
ss = " " + ss;
tt = " " + tt;
char[] s = ss.toCharArray();
char[] t = tt.toCharArray();
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + Math.abs(s[i] - t[i]);
int l = 1, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(sum, mid, max)) {
l = mid;
} else {
r = mid - 1;
}
}
return check(sum, r, max) ? r : 0;
}
boolean check(int[] nums, int mid, int max) {
for (int i = mid; i < nums.length; i++) {
int tot = nums[i] - nums[i - mid];
if (tot <= max) return true;
}
return false;
}
}
;二分出「滑动窗口长度」的复杂度为
,对于每个窗口长度,需要扫描一遍数组进行检查,复杂度为
,因此二分的复杂度为
。整体复杂度为
二分的本质与模板代码:
复杂度/计算量推算是否超时分析:
这是我们「刷穿 LeetCode」系列文章的第 No.*
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 */1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。