DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Longest Repeating Character Replacement

mediumSliding window

Problem statement

You are given a string s of uppercase English letters and an integer k. You may change at most k characters of s to any other uppercase letter. After the changes, return the length of the longest substring in which every character is the same letter.

Examples

Example 1

Input: s = "XYYXYYYX", k = 1

Output: 6

Explanation: Change the X at index 3 to Y. Indices 1 to 6 become "YYYYYY".

Example 2

Input: s = "QRST", k = 0

Output: 1

Explanation: No changes are allowed and all letters differ.

Hints

Approach

Slide one window across the string. Track letter counts inside it and top, the highest count any letter has reached.

  1. For each right, add s[right] to the counts and update top.
  2. If (right - left + 1) - top > k, the window needs too many changes: remove s[left] and move left forward by one.
  3. After the step, the window length right - left + 1 is a candidate answer.

The subtle part: top is never decreased when the left edge moves, so it can be stale. That is fine. The answer only grows when a letter reaches a new highest count, and a stale top can only keep the window at its current length, never report a length that isn't achievable. Because the window never shrinks by more than one per step, its size at the end is the answer.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
counts = [0] * 26
left = 0
top = 0 # highest count of one letter seen in any window so far
for right, ch in enumerate(s):
idx = ord(ch) - 65
counts[idx] += 1
top = max(top, counts[idx])
if (right - left + 1) - top > k: # too many letters to change
counts[ord(s[left]) - 65] -= 1
left += 1
return len(s) - left

Follow-up questions

  • Return the resulting substring and which letter it is made of.
  • Solve the binary version: given a string of 0s and 1s, find the longest run of 1s after flipping at most k zeros.

Frequently asked questions

The window only grows or slides; it never shrinks. So its final size, n - left, equals the largest size it ever reached, which is the answer.

It would be wrong if we reported every window as valid. We don't: the window keeps its size until some letter beats the old top, and only then does it grow. Recomputing the true maximum each step (scanning 26 counts) is also correct and still O(26·n) if you prefer to avoid the argument.

It is a harder sliding-window question that checks whether you can state a window's validity rule precisely. The same shape appears in "longest stretch of health checks that is all passing if we forgive up to k flaps".