Longest Repeating Character Replacement

Medium · Sliding Window

You are given a string made up of uppercase English letters and a non-negative integer k. You may change up to k characters in the string to any other uppercase letter, each change independent of the others. Return the length of the longest substring you can obtain (after such changes) that consists of a single repeated letter.

Examples

Input:  s = "XYYX", k = 2
Output: 4
Why:    Changing both X's to Y (or vice versa) uses at most 2 replacements and makes the whole string one repeated letter.

Input:  s = "AABABBA", k = 1
Output: 4
Why:    Flipping the single B inside "ABAB" segment lets you get a run of 4 same letters using only 1 replacement.

Input:  s = "ABCDE", k = 1
Output: 2
Why:    With only 1 replacement allowed, you can turn any adjacent pair into matching letters, giving a max run of 2.

Constraints

1 <= s.length <= 10^5, s consists of only uppercase English letters, 0 <= k <= s.length

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Longest Repeating Character Replacement

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Longest Repeating Character Replacement. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.