算法练习——替换后的最长重复字符

2021年2月2日LeetCode每日一题为424. 替换后的最长重复字符,遍历字符串,每次从起始下标再遍历一次,如果发现这个字符与起始字符不同,那么将修改次数减一,如果修改次数耗尽,则说明替换后的重复字符结束,退出循环。在计算长度的时候,除了终止位置减去起始位置外,还有能通过消耗修改次数来加长重复字符,因此需要加上修改次数,并判断是否超出数组长度,超出长度则最长为整个字符的长度,否则为加上修改次数的长度,即是使用两者最小值。代码如下:

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 characterReplacement(String s, int k) {
char[] array = s.toCharArray();
int begin = 0, ret = 0;
while (begin < array.length - 1 && array.length - begin >= ret) {
int n = k;
int i = begin + 1;
while (i < array.length) {
if (array[i] != array[begin]) {
if (n != 0) {
n--;
} else {
break;
}
}
i++;
}
ret = Math.max(ret, Math.min(i - begin + n, array.length));
begin++;
}
return ret;
}
}