424. Longest Repeating Character Replacement
mediumFind the longest substring you can convert into all-same letters by changing at most k characters. A canonical sliding-window-with-frequency-map problem with a clever invariant.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.
Constraints
1 <= s.length <= 10^5s consists of only uppercase English letters.0 <= k <= s.length
Examples
Example 1
s = "ABAB", k = 24Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2
s = "AABABBA", k = 14Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, of length 4.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
A window [left, right] is valid if (window_length - count_of_most_frequent_letter) <= k.
Hint 2
Slide a window with right. Whenever the window becomes invalid, increment left until it's valid again.
Hint 3
Track letter counts inside the window. The answer is the maximum valid window length you observe.
Solution approach
Reveal approach
Sliding window with a frequency map and a max-count optimisation. Maintain count[26] for the current window and maxCount = the highest single-letter count ever seen in any window. For each right in [0, n): increment count[s[right]] and update maxCount if higher; if (right - left + 1) - maxCount > k the window has too many changes, so increment count[s[left]]'s decrement and advance left by one. The clever bit: maxCount is never decreased when shrinking — that's fine because the answer only grows when a better maxCount appears, so a stale maxCount can only keep the answer at its current best. Return n - left at the end (equivalent to the running window length since right reaches n-1). O(n) time, O(1) space (26-letter alphabet).
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- sliding-window
- hash-map
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Meta
- Amazon
- Microsoft
More Strings practice problems
- 3. Longest Substring Without Repeating Characters
- 5. Longest Palindromic Substring
- 6. Zigzag Conversion
- 14. Longest Common Prefix
- 20. Valid Parentheses
- 28. Find the Index of the First Occurrence in a String
- 49. Group Anagrams
- 58. Length of Last Word