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