Sliding Window · 057Medium
Longest Repeating Character Replacement
Given a string s of uppercase English letters and an integer k, you may change at most k characters to any other uppercase letter. Return the length of the longest substring containing a single repeated letter.
Constraints
- 1 <= s.length <= 10^5
- s consists of uppercase English letters only.
- 0 <= k <= s.length
Examples
characterReplacement("ABAB", 2) -> 4 // change both A or both B
characterReplacement("AABABBA", 1) -> 4 // "AABA" -> "AAAA"
characterReplacement("A", 0) -> 1
characterReplacement("AAAA", 0) -> 4 // k = 0, all identical
characterReplacement("ABCDE", 1) -> 2 // k = 1 buys only one neighbour
characterReplacement("AB", 5) -> 2 // k larger than the stringEdge cases
- k = 0 means the longest run of one repeated character.
- k may exceed the string length.
Show the target complexity (spoiler)
- Naive
- O(n^2 * 26) time — test every substring against every target letter.
- Target
- O(n) time, O(26) space — a sliding window tracking character counts and the max count seen, shrinking whenever the window turns invalid.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/03-sliding-window/057-longest-repeating-character-replacement.js ./practice c 057