算法练习——尽可能使字符串相等

2021年2月5日LeetCode每日一题为1208. 尽可能使字符串相等,其最大值要求是子串,因此需要滑动窗口来计算转换后的最长长度。首先将两个数组的每个对应字符变换的代价记录到数组中,用一个变量保存代价总和,一个变量保存长度。循环代价数组,累加代价并使当前长度+1,然后判断是否超过了允许的最大代价,由于本次变换超出最大代价,因此本变换是不允许的,记录下符合条件的长度并当前代价降低到最大代价范围内。代码如下:

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
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
if (s.equals(t)) {
return s.length();
}
int maxChange = 0;
char[] sArray = s.toCharArray();
char[] tArray = t.toCharArray();
int[] cost = new int[sArray.length];
for (int i = 0; i < sArray.length; i++) {
cost[i] = Math.abs(sArray[i] - tArray[i]);
}
int sum = 0, change = 0;
for (int i = 0; i < cost.length; i++) {
sum += cost[i];
change++;
while (sum > maxCost && change > 0) {
change--;
sum -= cost[i - change];
maxChange = Math.max(change, maxChange);
}
}
return Math.max(change, maxChange);
}
}