LeetCode-424. Longest Repeating Character Replacement

LeetCode-424. Longest Repeating Character Replacement

Given a string ​​s​​​ that consists of only uppercase English letters, you can perform at most ​​k​​ operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string 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 = 2Output:4Explanation:Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:s = "AABABBA", k = 1Output:4Explanation:Replace the one 'A' in the middle with 'B' and form "AABBBBA".The substring "BBBB" has the longest repeating letters, which is 4.

题解：

左右指针滑动窗口，使用一个表记录每个字母在窗口内出现的次数，max维护窗口内某个字母出现的最大次数，如果当前窗口大小减去max大于k，那么滑动左窗口，并且维护最大值。

c++：

class Solution {public: int characterReplacement(string s, int k) { if(s.size() <= k) { return s.size(); } vector temp(26); int left = 0, right = 0; int maxnum = 0; int res = 0; for(; right < s.size(); right++) { temp[s[right] - 'A']++; maxnum = max(maxnum, temp[s[right] - 'A']); while(right - left + 1 - maxnum > k) { temp[s[left++] - 'A']--; } res = max(res, right - left + 1); } return res; }};

go：

func characterReplacement(s string, k int) int { l := len(s) if l <= k { return l } max, res, left, right := 0, 0, 0, 0 tmp := make([]int, 26) for ; right < l; right++ { tmp[s[right] - 'A']++; max = int(math.Max(float64(tmp[s[right] - 'A']), float64(max))) for right - left + 1 - max > k { tmp[s[left] - 'A']-- left++ } res = int(math.Max(float64(res), float64(right - left + 1))) } return res}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。