Formatted question description: https://leetcode.ca/all/424.html
424. Longest Repeating Character Replacement
Level
Medium
Description
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 substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string’s length and k will not exceed 10^{4}.
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.
Solution
Use sliding window. Use a map to store each letter and the number of occurrences of each letter. Initialize low
and high
to 0, and use maxCount
to store the maximum numbers of the same letter met so far, which is initially 0.
Loop over s
using index high
. Obtain the letter at index high
, update the number of occurrences of the letter in the map, and update maxCount
. If the current substring’s length high  low + 1
is greater than maxCount + k
, then move low
forward by 1 step. Move high
forward by 1 step after the letter is dealt with. Finally, return s.length()  low
.

class Solution { public int characterReplacement(String s, int k) { if (s == null  s.length() == 0) return 0; Map<Character, Integer> map = new HashMap<Character, Integer>(); int maxCount = 0; int low = 0, high = 0; int length = s.length(); while (high < length) { char highC = s.charAt(high); int highCount = map.getOrDefault(highC, 0); highCount++; map.put(highC, highCount); maxCount = Math.max(maxCount, highCount); if (high  low + 1 > maxCount + k) { char lowC = s.charAt(low); int lowCount = map.getOrDefault(lowC, 0); lowCount; if (lowCount > 0) map.put(lowC, lowCount); else map.remove(lowC); low++; } high++; } return length  low; } }

// OJ: https://leetcode.com/problems/longestrepeatingcharacterreplacement/ // Time: O(N) // Space: O(1) class Solution { public: int characterReplacement(string s, int k) { int i = 0, j = 0, cnt[26] = {}, ans = 0, N = s.size(); while (j < N) { cnt[s[j++]  'A']++; while (j  i  *max_element(cnt, cnt + 26) > k) cnt[s[i++]  'A']; ans = max(ans, j  i); } return ans; } };

from collections import deque class Solution(object): def characterReplacement(self, s, k): """ :type s: str :type k: int :rtype: int """ ans = 0 d = {} start = 0 maxCount = 0 window = deque([]) for end in range(0, len(s)): d[s[end]] = d.get(s[end], 0) + 1 maxCount = max(maxCount, d[s[end]]) if end  start + 1  maxCount > k: d[s[start]] = 1 start += 1 ans = max(ans, end  start + 1) return ans