Longest Substring After At Most K Character Replacements
Implement longestSubstringAfterKReplacements
Given a string
s and an integer k, return the length of the longest substring that can be turned into one repeated character by changing at most k of its characters.
A window of length L is achievable with at most k replacements exactly when L - maxFreq ≤ k, where maxFreq is the count of the window's most frequent character — every other character in the window is the one that would need replacing. The sliding windowSliding WindowMaintaining a running result over a contiguous range that grows or shrinks one element at a time, instead of recomputing the result for every range from scratch. technique grows the window right while tracking a frequency count and the running maxFreq, and shrinks from the left by one whenever that condition breaks. maxFreq is allowed to go stale after a shrink — it never causes an invalid window to be accepted, since the tracked answer only advances when a genuinely longer valid window is found — so the whole scan still runs in O(n).
Example 1:
Input: s = "aabcb", k = 1
Output: 3
Example 2:
Input: s = "abab", k = 2
Output: 4
Example 3:
Input: s = "aaaa", k = 0
Output: 4
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ s.length ≤ 10⁵ - ●
0 ≤ k ≤ s.length - ●
s consists of lowercase English letters only
s =
aabcb
k =
1