Longest Repeating Character Replacement
01 · Problem
You are given a string s of uppercase English letters and an integer k. You may perform the following operation at most k times: pick any position in the string and change its character to any other uppercase letter.
Return the length of the longest substring containing only one distinct letter that you can obtain after performing at most k operations.
02 · Examples
s = "XXYXX", k = 1
5
Replace the single 'Y' with 'X' to get "XXXXX", a run of 5 identical letters.
s = "PQPQQ", k = 1
4
Replace the 'P' at index 2 with 'Q' to get "PQQQQ", which contains "QQQQ" of length 4.
s = "ABCDE", k = 1
2
Changing one letter can make at most two adjacent letters equal, e.g. "AACDE", so the answer is 2.
03 · Constraints
- 011 <= s.length <= 105
- 02s consists of only uppercase English letters
- 030 <= k <= s.length
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.