424 Longest Repeating Character Replacement

424. Longest Repeating Character Replacement​
1. Question
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at mostktimes. 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 andkwill not exceed 104.
Example 1:
1
Input: s = "ABAB", k = 2
2
​
3
Output: 4
4
​
5
Explanation: Replace the two 'A's with two 'B's or vice versa.
Copied!
Example 2:
1
Input: s = "AABABBA", k = 1
2
​
3
Output: 4
4
​
5
Explanation: 
6
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
7
The substring "BBBB" has the longest repeating letters, which is 4.
Copied!
2. Implementation
(1) Two Pointer + Hash
思路: 这道题的本质是问找到一个最长的substring满足，该substring的长度减substring中最多重复的character的个数是小于等于k的。所以我们维护一个变量maxCount, 从左向右扫s， maxCount记录目前最多重复的character的个数，当substring的长度减去maxCount的值大于k时，我们需要更新substring的起点。
1
class Solution {
2
    public int characterReplacement(String s, int k) {
3
        if (s.length() <= k) {
4
            return s.length();
5
        }
6
​
7
        int start = 0, end = 0, maxCount = 0, maxLen = 0;
8
        int[] map = new int[256];
9
​
10
        while (end < s.length()) {
11
            ++map[s.charAt(end)];
12
            maxCount = Math.max(maxCount, map[s.charAt(end)]);
13
            ++end;
14
​
15
            if (end - start - maxCount > k) {
16
                --map[s.charAt(start)];
17
                ++start;
18
            }
19
            maxLen = Math.max(maxLen, end - start);
20
        }
21
        return maxLen;
22
    }
23
}
Copied!
3. Time & Space Complexity
Two Pointer + Hash: 时间复杂度O(n), 空间复杂度O(1)

395 Longest Substring with At Least K Repeating Characters

438 Find All Anagrams in a String

Last modified 2yr ago

Copy link

Contents

424. Longest Repeating Character Replacement

1. Question

2. Implementation

3. Time & Space Complexity

424. Longest Repeating Character Replacement​

1. Question

2. Implementation

3. Time & Space Complexity

424. Longest Repeating Character Replacement