LeetCode Longest Repeating Character Replacement

LeetCode Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

给定一个字符串s,可以把s中最多k个字符换成另一个字符,问这样做之后,最大能得到多长的重复字符的字符串。

比如样例一s="ABAB",k=2,把两个A都改为B之后,所有字符都变成了B,长度为4。

本题使用滑动窗口来解。每次我们统计窗口内出现频率最多的字符,那么最好的办法就是把窗口内其他字符全换成最高频的字符,条件就是其他字符的数量要不超过k,这样替换的次数才不会超过k。

在滑动窗口的时候,如果其他字符的数量超过k了,则需要缩减窗口大小,也就是把窗口左端往右滑。

代码如下:

class Solution {
public:
	int characterReplacement(string s, int k) {
		int ans = 0, n = s.size();
		vector<int> count(26, 0);
		int start = 0;
		for (int end = 0; end < n; ++end) {
			++count[s[end] - 'A'];
			while (end - start + 1 - *max_element(count.begin(), count.end()) > k) {
				--count[s[start++] - 'A'];
			}
			ans = max(ans, end - start + 1);
		}
		return ans;
	}
};

本代码提交AC,用时29MS。渐进复杂度应该是O(n^2)的。

讨论区还有O(n)的方法,但是我看了好久都没理解,为啥max不会减少,为啥返回的直接是s.length()-start。

Leave a Reply

Your email address will not be published. Required fields are marked *