Skip to main content

424. Longest Repeating Character Replacement

medium

Find 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 Alex Chen, 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^5
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Examples

Example 1

Input
s = "ABAB", k = 2
Output
4

Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2

Input
s = "AABABBA", k = 1
Output
4

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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
  • Google

Practice these live with InterviewChamp.AI

Drill Longest Repeating Character Replacement and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →