mediumSliding WindowPure DSA~26 min
Longest Run After K Flips
A categorical event stream is encoded as uppercase letters. You may relabel at most k events to any single category to lengthen a uniform run. Find the longest run of one category achievable after at most k relabels.
Problem
Given a string s of uppercase letters and an integer k, return the length of the longest substring containing a single repeated letter after replacing at most k characters.
Input
A string s of length n (1 ≤ n ≤ 10^5) of uppercase letters and integer k (0 ≤ k ≤ n).
Output
A single integer — the longest achievable uniform run.
Constraints
- 1 ≤ n ≤ 100,000
- 0 ≤ k ≤ n
- Only uppercase English letters
Examples
Example 1
Input
s = "AABABBA", k = 1
Output
4
Replacing one B in "AABA" (or one A in "ABBA") yields a run of 4 identical letters.
Example 2
Input
s = "ABCDE", k = 0
Output
1
With no replacements, the best uniform run is a single character.