leetcode 424 Longest Repeating Character Replacement
z
 2019-04-18 21:31:43  

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:

1
2
3
4
5
6
7
8
Input:
s = "ABAB", k = 2

Output:
4

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

Example 2:

1
2
3
4
5
6
7
8
9
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.
  • 用一个滑动窗口 <start, end> ，统计当前窗口中字符信息;
  • 窗口中的字符信息用一个count数组来保存，每当end向后移动，count[s[end]-‘A’] ++, 当start向后移动时， count[s[start]-‘A’] —;
  • 用一个currentMaxt来保存窗口在滑动过程中，出现字符最多的字符的数目。
  • 可以知道，满足要求的子串中，肯定包含了currentMax，这样的话，只需要在保存满足k限制的最大的窗口，就可以得到答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int start = 0;
        int end = 0;
        int currentMax = 0;
        int ans = 0;
        for (end=0; end<s.length(); end++) {
            int i = s.charAt(end)-'A';
            count[i] ++;
            currentMax = Math.max(currentMax, count[i]);
            while (end-start+1-currentMax > k) {
                count[s.charAt(start)-'A'] --;
                start ++;
            }
            ans = Math.max(ans, end-start+1);
        }
        return ans;
    }
}

python version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        start, current_max, ans = 0, 0, 0
        counter = collections.Counter()
        for i in range(len(s)):
            counter[s[i]] += 1
            current_max = len(counter.most_common()) # 
            while (i - start + 1 - current_max) > k:
                counter[s[start]] -= 1
                start += 1
            ans = max(ans, i - start + 1)
        return ans