424. Longest Repeating Character Replacement
## description
## 424. Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
1Input: s = "ABAB", k = 2
2Output: 4
3Explanation: Replace the two 'A's with two 'B's or vice versa.Example 2:
1Input: s = "AABABBA", k = 1
2Output: 4
3Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
4The substring "BBBB" has the longest repeating letters, which is 4.
5There may exists other ways to achieve this answer too.- –1 <= s.length <= 105
- –s consists of only uppercase English letters.
- –0 <= k <= s.length
Constraints:
## notes
### Intuition
In any window, the minimum replacements needed equals window_length - max_frequency_of_any_char. If this exceeds k, shrink the window. Otherwise, we have a valid window where we can make all characters the same.
### Implementation
Maintain a frequency array for 26 characters and track the maximum frequency seen. For each right pointer position, increment the character's frequency and update max frequency. If window_size - max_freq > k, the window is invalid—shrink from the left by decrementing that character's frequency and moving l. Track the maximum valid window length.
### Edge-cases
Window size is r - l + 1. The max frequency doesn't need to decrease when shrinking—if it was valid before, using that max won't make the window smaller than it could be.
- –Time: O(n) — each character processed once
- –Space: O(1) — frequency array is fixed at 26 elements
### Complexity
## solution
1class Solution:
2 def char2idx(self, c: str) -> int:
3 return ord(c) - ord('A')
4
5 def characterReplacement(self, s: str, k: int) -> int:
6 freq = [0] * 26
7 l, max_f, max_len = 0, 0, 0
8 for r in range(len(s)):
9 freq[self.char2idx(s[r])] += 1
10 max_f = max(max_f, freq[self.char2idx(s[r])])
11
12 while (r - l + 1) - max_f > k:
13 freq[self.char2idx(s[l])] -= 1
14 l += 1
15
16 max_len = max(max_len, r - l + 1)
17 return max_len
18
19
20
21
22if __name__ == "__main__":
23 # Include one-off tests here or debugging logic that can be run by running this file
24 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
25 solution = Solution()
26