Longest Repeating Character Replacement

MediumSliding Windowsliding window

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s made up of uppercase English letters, along with an integer k. In a single operation you may pick any position in s and overwrite the character there with any other uppercase English letter. You are allowed to perform at most k such operations. Your goal is to make some contiguous block of s consist of a single repeated letter. Return the length of the **longest** substring you can turn into one made entirely of the same letter, using no more than k replacements. In other words, find the maximum length window such that, after changing at most k of its characters, every character in the window is identical.

Examples

Input: s = "ABAB", k = 2
Output: 4
Replace the two `A`s with `B`s (or the two `B`s with `A`s) to get a block of four identical letters.
Input: s = "AABABBA", k = 1
Output: 4
Change the single `A` in the middle of "ABAB" to get "AABBBBA"; the substring "BBBB" has length 4. No window of length 5 can be fixed with just one replacement.
Input: s = "AAAA", k = 0
Output: 4
The whole string is already a single repeated letter, so no replacements are needed.

Constraints

  • 1 <= len(s) <= 100000
  • `s` consists only of uppercase English letters (`A`-`Z`)
  • 0 <= k <= len(s)

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More sliding window problems