Longest Repeating Character Replacement
The key idea
Slide a window and track the count of its most frequent letter. The window is valid when (window length - count of the most frequent letter) <=
k, because that difference is exactly how many letters you must replace to make the whole window one repeated character. Grow the right edge always; nudge the left edge forward only when the window stops being valid, so the window size never shrinks.Problem
You are given a string s and an integer k. You can choose any character of s and change it to any other uppercase English letter. 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.
Constraints
- 1 <=
s.length<= 10^5 sconsists of only uppercase English letters- 0 <=
k<=s.length
Examples
Input: s = "ABAB", k = 2
Output: 4
Input: s = "AABABBA", k = 1
Output: 4
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Sliding Window MaximumHARD
- Substring with Concatenation of All WordsHARD