题目描述
给你两个长度相同的字符串，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^50 <= maxCost <= 10^6s 和 t 都只含小写英文字母。
解法
方法一：前缀和 + 二分查找
我们可以创建一个长度为 $n + 1$ 的数组 $f$，其中 $f[i]$ 表示字符串 $s$ 的前 $i$ 个字符与字符串 $t$ 的前 $i$ 个字符的 ASCII 码值的差的绝对值之和。这样，我们就可以通过 $f[j + 1] - f[i]$ 来计算字符串 $s$ 的第 $i$ 个字符到第 $j$ 个字符的 ASCII 码值的差的绝对值之和，其中 $0 \leq i \leq j < n$。
注意到长度具有单调性，即如果存在长度为 $x$ 的子串满足条件，那么长度为 $x - 1$ 的子串也一定满足条件。因此，我们可以使用二分查找的方法来求解最大长度。
我们定义函数 $check(x)$，表示是否存在长度为 $x$ 的子串满足条件。在该函数中，我们只需要枚举所有长度为 $x$ 的子串，判断其是否满足条件即可。如果存在满足条件的子串，那么函数返回 true，否则返回 false。
接下来，我们定义二分查找的左边界 $l$ 为 $0$，右边界 $r$ 为 $n$。在每一步中，我们令 $mid = \lfloor \frac{l + r + 1}{2} \rfloor$，如果函数 $check(mid)$ 的返回值为 true，那么我们将左边界更新为 $mid$，否则我们将右边界更新为 $mid - 1$。在二分查找结束后，我们得到的左边界即为答案。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
def check(x):
for i in range(n):
j = i + mid - 1
if j < n and f[j + 1] - f[i] <= maxCost:
return True
return False
n = len(s)
f = list(accumulate((abs(ord(a) - ord(b)) for a, b in zip(s, t)), initial=0))
l, r = 0, n
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
return l
|
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 | class Solution {
private int maxCost;
private int[] f;
private int n;
public int equalSubstring(String s, String t, int maxCost) {
n = s.length();
f = new int[n + 1];
this.maxCost = maxCost;
for (int i = 0; i < n; ++i) {
int x = Math.abs(s.charAt(i) - t.charAt(i));
f[i + 1] = f[i] + x;
}
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >>> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private boolean check(int x) {
for (int i = 0; i + x - 1 < n; ++i) {
int j = i + x - 1;
if (f[j + 1] - f[i] <= maxCost) {
return true;
}
}
return false;
}
}
|
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 | class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int n = s.size();
int f[n + 1];
f[0] = 0;
for (int i = 0; i < n; ++i) {
f[i + 1] = f[i] + abs(s[i] - t[i]);
}
auto check = [&](int x) -> bool {
for (int i = 0; i + x - 1 < n; ++i) {
int j = i + x - 1;
if (f[j + 1] - f[i] <= maxCost) {
return true;
}
}
return false;
};
int l = 0, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};
|
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 | func equalSubstring(s string, t string, maxCost int) int {
n := len(s)
f := make([]int, n+1)
for i, a := range s {
f[i+1] = f[i] + abs(int(a)-int(t[i]))
}
check := func(x int) bool {
for i := 0; i+x-1 < n; i++ {
if f[i+x]-f[i] <= maxCost {
return true
}
}
return false
}
l, r := 0, n
for l < r {
mid := (l + r + 1) >> 1
if check(mid) {
l = mid
} else {
r = mid - 1
}
}
return l
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
方法二：双指针
我们可以维护两个指针 $j$ 和 $i$，初始时 $i = j = 0$；维护一个变量 $sum$，表示下标区间 $[i,..j]$ 之间的 ASCII 码值的差的绝对值之和。在每一步中，我们将 $i$ 向右移动一位，然后更新 $sum = sum + |s[i] - t[i]|$。如果 $sum \gt maxCost$，那么我们就循环将指针 $j$ 向右移动，并且在移动过程中不断减少 $sum$ 的值，直到 $sum \leq maxCost$。然后我们更新答案，即 $ans = \max(ans, i - j + 1)$。
最后返回答案即可。
时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
n = len(s)
sum = j = 0
ans = 0
for i in range(n):
sum += abs(ord(s[i]) - ord(t[i]))
while sum > maxCost:
sum -= abs(ord(s[j]) - ord(t[j]))
j += 1
ans = max(ans, i - j + 1)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int n = s.length();
int sum = 0;
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
sum += Math.abs(s.charAt(i) - t.charAt(i));
while (sum > maxCost) {
sum -= Math.abs(s.charAt(j) - t.charAt(j));
++j;
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int n = s.size();
int ans = 0, sum = 0;
for (int i = 0, j = 0; i < n; ++i) {
sum += abs(s[i] - t[i]);
while (sum > maxCost) {
sum -= abs(s[j] - t[j]);
++j;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func equalSubstring(s string, t string, maxCost int) (ans int) {
var sum, j int
for i := range s {
sum += abs(int(s[i]) - int(t[i]))
for ; sum > maxCost; j++ {
sum -= abs(int(s[j]) - int(t[j]))
}
if ans < i-j+1 {
ans = i - j + 1
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|