class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
}
};
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^50 <= maxCost <= 10^6s 和 t 都只含小写英文字母。原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.6 MB, 提交时间: 2023-05-29 18:02:01
func equalSubstring(s string, t string, maxCost int) (maxLen int) {
n := len(s)
diff := make([]int, n)
for i, ch := range s {
diff[i] = abs(int(ch) - int(t[i]))
}
sum, start := 0, 0
for end, d := range diff {
sum += d
for sum > maxCost {
sum -= diff[start]
start++
}
maxLen = max(maxLen, end-start+1)
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 96 ms, 内存消耗: 17.6 MB, 提交时间: 2023-05-29 18:01:44
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
n = len(s)
diff = [abs(ord(sc) - ord(tc)) for sc, tc in zip(s, t)]
maxLength = start = end = 0
total = 0
while end < n:
total += diff[end]
while total > maxCost:
total -= diff[start]
start += 1
maxLength = max(maxLength, end - start + 1)
end += 1
return maxLength
javascript 解法, 执行用时: 72 ms, 内存消耗: 42.4 MB, 提交时间: 2023-05-29 18:01:19
/**
* @param {string} s
* @param {string} t
* @param {number} maxCost
* @return {number}
*/
var equalSubstring = function(s, t, maxCost) {
const n = s.length;
const diff = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
diff[i] = Math.abs(s[i].charCodeAt() - t[i].charCodeAt());
}
let maxLength = 0;
let start = 0, end = 0;
let sum = 0;
while (end < n) {
sum += diff[end];
while (sum > maxCost) {
sum -= diff[start];
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
end++;
}
return maxLength;
};
java 解法, 执行用时: 6 ms, 内存消耗: 42.3 MB, 提交时间: 2023-05-29 18:01:01
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int n = s.length();
int[] diff = new int[n];
for (int i = 0; i < n; i++) {
diff[i] = Math.abs(s.charAt(i) - t.charAt(i));
}
int maxLength = 0;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += diff[end];
while (sum > maxCost) {
sum -= diff[start];
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
end++;
}
return maxLength;
}
}
java 解法, 执行用时: 13 ms, 内存消耗: 42.4 MB, 提交时间: 2023-05-29 18:00:51
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int n = s.length();
int[] accDiff = new int[n + 1];
for (int i = 0; i < n; i++) {
accDiff[i + 1] = accDiff[i] + Math.abs(s.charAt(i) - t.charAt(i));
}
int maxLength = 0;
for (int i = 1; i <= n; i++) {
int start = binarySearch(accDiff, i, accDiff[i] - maxCost);
maxLength = Math.max(maxLength, i - start);
}
return maxLength;
}
public int binarySearch(int[] accDiff, int endIndex, int target) {
int low = 0, high = endIndex;
while (low < high) {
int mid = (high - low) / 2 + low;
if (accDiff[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
javascript 解法, 执行用时: 88 ms, 内存消耗: 42.3 MB, 提交时间: 2023-05-29 18:00:35
/**
* @param {string} s
* @param {string} t
* @param {number} maxCost
* @return {number}
*/
var equalSubstring = function(s, t, maxCost) {
const n = s.length;
const accDiff = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
accDiff[i + 1] = accDiff[i] + Math.abs(s[i].charCodeAt() - t[i].charCodeAt());
}
let maxLength = 0;
for (let i = 1; i <= n; i++) {
const start = binarySearch(accDiff, i, accDiff[i] - maxCost);
maxLength = Math.max(maxLength, i - start);
}
return maxLength;
};
const binarySearch = (accDiff, endIndex, target) => {
let low = 0, high = endIndex;
while (low < high) {
const mid = Math.floor((high - low) / 2) + low;
if (accDiff[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
golang 解法, 执行用时: 8 ms, 内存消耗: 3.6 MB, 提交时间: 2023-05-29 18:00:13
func equalSubstring(s string, t string, maxCost int) (maxLen int) {
n := len(s)
accDiff := make([]int, n+1)
for i, ch := range s {
accDiff[i+1] = accDiff[i] + abs(int(ch)-int(t[i]))
}
for i := 1; i <= n; i++ {
start := sort.SearchInts(accDiff[:i], accDiff[i]-maxCost)
maxLen = max(maxLen, i-start)
}
return
}
func abs(x int) int { if x < 0 { return -x }; return x }
func max(a, b int) int { if a > b { return a }; return b }
python3 解法, 执行用时: 76 ms, 内存消耗: 21.4 MB, 提交时间: 2023-05-29 17:59:22
# 前缀和 + 二分查找
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
n = len(s)
accDiff = [0] + list(accumulate(abs(ord(sc) - ord(tc)) for sc, tc in zip(s, t)))
maxLength = 0
for i in range(1, n + 1):
start = bisect.bisect_left(accDiff, accDiff[i] - maxCost)
maxLength = max(maxLength, i - start)
return maxLength
python3 解法, 执行用时: 80 ms, 内存消耗: 17.5 MB, 提交时间: 2023-05-29 17:58:41
'''
对于每一对下标相等的字符，s[i]和t[i]，
把它们转化成相等的 cost 是已知的，
cost = abs(ord(t[i]) - ord(s[i]))，
所以我们可以直接生成一个数组 record， record[i] 就表示把 s[i] 和 t[i] 转化成相等的 cost，
接着问题就转化为：
在一个数组中，在连续子数组的和小于等于 maxCost 的情况下，
找到最长的连续子数组长度。
因此可以用滑动窗口解题。
'''
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
n = len(s)
record = []
for i in range(n):
record.append(abs(ord(t[i]) - ord(s[i])))
start, end = 0, 0
windowsum = 0
res = 0
for end in range(n):
# print windowsum, start, end, res
windowsum += record[end]
while windowsum > maxCost:
res = max(res, end - start)
windowsum -= record[start]
start += 1
res = max(res, end - start + 1)
return res