题目描述 这是 LeetCode 上的 1208. 尽可能使字符串相等 ,难度为 中等 。
给你两个长度相同的字符串,s
和 t
。
将 s
中的第 i
个字符变到 t
中的第 i
个字符需要 |s[i] - t[i]|
的开销(开销可能为 0),也就是两个字符的 ASCII
码值的差的绝对值。
用于变更字符串的最大预算是 maxCost
。
在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
如果你可以将 s
的子字符串转化为它在 t
中对应的子字符串,则返回可以转化的最大长度。
如果 s
中没有子字符串可以转化成 t
中对应的子字符串,则返回 0。
示例 1:
输入:s = "abcd" , t = "bcdf" , maxCost = 3 输出:3 解释:s 中的 "abc" 可以变为 "bcd" 。开销为 3 ,所以最大长度为 3 。
示例 2:
输入:s = "abcd" , t = "cdef" , maxCost = 3 输出:1 解释:s 中的任一字符要想变成 t 中对应的字符,其开销都是 2 。因此,最大长度为 1 。
示例 3:
输入:s = "abcd" , t = "acde" , maxCost = 0 输出:1 解释:a -> a , cost = 0 ,字符串未发生变化,所以最大长度为 1 。
提示:
$1 <= s.length, t.length <= 10^5$
$0 <= maxCost <= 10^6$
s
和 t
都只含小写英文字母。
前缀和 + 二分 + 滑动窗口 给定了长度相同的 s
和 t
,那么对于每一位而言,修改的成本都是相互独立而确定的。
我们可以先预处理出修改成本的前缀和数组 sum
。
当有了前缀和数组之后,对于任意区间 [i,j]
的修改成本,便可以通过 sum[j] - sum[i - 1]
得出。
那么接下来我们只需要找出成本不超过 maxCost
的最大长度区间,这个长度区间其实就是滑动窗口长度,滑动窗口长度的范围为 [1, n]
(n 为字符串的长度)。
通过枚举来找答案可以吗?
我们可以通过数据范围大概分析一下哈,共有 n
个滑动窗口长度要枚举,复杂度为 $O(n)$,对于每个滑动窗口长度,需要对整个前缀和数组进行滑动检查,复杂度为 $O(n)$。也就是整体复杂度是 $O(n^2)$ 的。
数据范围是 $10^5$,那么单个样本的计算量是 $10^{10}$,计算机单秒肯定算不完,会超时 ~
所以我们直接放弃通过枚举的朴素做法。
那么如何优化呢?其实有了对于朴素解法的分析之后,无非就是两个方向:
优化第一个 $O(n)$:减少需要枚举的滑动窗口长度
优化第二个 $O(n)$:实现不完全滑动前缀和数组,也能确定滑动窗口长度是否合法
事实上第 2 点是无法实现的,我们只能「减少需要枚举的滑动窗口长度」。
一个 $O(n)$ 的操作往下优化,通常就是优化成 $O(\log{n})$,$O(\log{n})$ 基本上我们可以先猜一个「二分」查找。
然后我们再来分析是否可以二分:假设我们有满足要求的长度 ans
,那么在以 ans
为分割点的数轴上(数轴的范围是滑动窗口长度的范围:[1, n]
):
所有满足 <= ans
的点的修改成本必然满足 <= maxCost
所有满足 > ans
的点的修改成本必然满足 > maxCost
(否则 ans
就不会是答案)
因此 ans
在数轴 [1, n]
上具有二段性,我们可以使用「二分」找 ans
。得证「二分」的合理性。
可见二分的本质是二段性,而非单调性。
编码细节:
为了方便的预处理前缀和和减少边界处理,我会往字符串头部添加一个空格,使之后的数组下标从 1 开始
二分出来滑动窗口长度,需要在返回时再次检查,因为可能没有符合条件的有效滑动窗口长度
Java 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int equalSubstring (String ss, String tt, int max) { int n = ss.length(); ss = " " + ss; tt = " " + tt; char [] s = ss.toCharArray(), 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 ; } }
C++ 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : int equalSubstring (string ss, string tt, int max) { int n = ss.length (); ss = " " + ss; tt = " " + tt; vector<int > sum (n + 1 , 0 ) ; for (int i = 1 ; i <= n; i++) sum[i] = sum[i - 1 ] + abs (ss[i] - tt[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 ; } bool check (const vector<int >& nums, int mid, int max) { for (int i = mid; i < nums.size (); i++) { int tot = nums[i] - nums[i - mid]; if (tot <= max) return true ; } return false ; } };
Python 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def equalSubstring (self, ss: str , tt: str , maxv: int ) -> int : n = len (ss) ss, tt = " " + ss, " " + tt sumv = [0 ] * (n + 1 ) for i in range (1 , n + 1 ): sumv[i] = sumv[i - 1 ] + abs (ord (ss[i]) - ord (tt[i])) l, r = 1 , n while l < r: mid = l + r + 1 >> 1 if self.check(sumv, mid, maxv): l = mid else : r = mid - 1 return l if self.check(sumv, r, maxv) else 0 def check (self, nums, mid, maxv ): for i in range (mid, len (nums)): tot = nums[i] - nums[i - mid] if tot <= maxv: return True return False
TypeScript 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function check (nums: number [], mid: number , max: number ): boolean { for (let i : number = mid; i <= nums.length ; i++) { const tot : number = nums[i] - nums[i - mid]; if (tot <= max) return true ; } return false ; }function equalSubstring (ss: string , tt: string , max: number ): number { const n : number = ss.length ; ss = " " + ss; tt = " " + tt; const sum : number [] = [0 ]; for (let i : number = 1 ; i <= n; i++) sum[i] = sum[i - 1 ] + Math .abs (ss.charCodeAt (i) - tt.charCodeAt (i)); let l : number = 1 , r : number = n; while (l < r) { const mid : number = l + r + 1 >> 1 ; if (check (sum, mid, max)) l = mid; else r = mid - 1 ; } return check (sum, r, max) ? r : 0 ; };
时间复杂度:预处理出前缀和的复杂度为 $O(n)$;二分出「滑动窗口长度」的复杂度为 $O(\log{n})$,对于每个窗口长度,需要扫描一遍数组进行检查,复杂度为 $O(n)$,因此二分的复杂度为 $O(n\log{n})$。整体复杂度为 $O(n\log{n})$
空间复杂度:使用了前缀和数组。复杂度为 $O(n)$
最后 这是我们「刷穿 LeetCode」系列文章的第 No.1208
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。