loading

Longest Repeating Character Replacement — Step-by-Step Visualization

mediumLeetCode #424Hash TableStringSliding Window

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.

Algorithm Pattern

Sliding Window

Key Idea

The window is valid when (window length - max character frequency) ≤ k. Expand R every step; shrink L only when the window becomes invalid.

Step-by-Step Approach

  1. Maintain a count map of characters in the window.
  2. After adding s[r], check if (r - l + 1) - max(count.values()) > k.
  3. If so, decrement count[s[l]] and advance l.
  4. Update res = max(res, r - l + 1).

Common Gotchas

  • We only need the max frequency we've ever seen — shrinking the window by 1 is enough.
  • The key insight: replacements needed = window_size - max_freq.

Related Problems

← All problems