Longest Repeating Character Replacement
MediumSliding Window · SalesForce
You are given a string s of uppercase English letters and an integer k.
You may change at most k characters of s in total; each change replaces one character with any uppercase letter. After your changes, look for the longest substring (a contiguous run of characters) in which every character is the same letter.
Return the length of the longest such substring you can achieve.
Example 1
- Input:
- s = "CBBACBB", k = 2
- Output:
- 6
- Explanation
- Take the whole string
CBBACBB: it has fourBcharacters and three others. Three changes would be needed, which is too many, but the windowBBACBB(indices 1 to 6) has fourBand only two non-Bcharacters, so changing those two gives a run of 6.
Example 2
- Input:
- s = "BAAAB", k = 2
- Output:
- 5
- Explanation
- Changing both
Bcharacters toAuses exactly the 2 allowed changes and turns the whole string intoAAAAA.
Example 3
- Input:
- s = "ABCD", k = 0
- Output:
- 1
- Explanation
- No changes are allowed and no two neighbours match, so the longest run is a single character.
Constraints
- 1 ≤
s.length≤ 105 - 0 ≤
k≤s.length scontains only uppercase English letters