mafeshsho8lmafeshsho8l
Get Started
All coding questions

Longest Repeating Character Replacement

medium
NeetCode 150stringssliding-window

Problem

Given a string of uppercase letters and a budget k, find the length of the longest substring you can make all-identical by replacing at most k characters.

Examples

Input: s = "ABAB", k = 2
Output: 4
Replace the two B's to get "AAAA".
Input: s = "AABABBA", k = 1
Output: 4
One replacement yields a run of four equal letters.

Constraints

  • • 1 <= s.length <= 10^5
  • • 0 <= k <= s.length
  • • Uppercase English letters only
Hints(tap to reveal)
  • 1. A window is valid if its length minus its most frequent letter count is at most k.
  • 2. Track letter counts inside the window.
Optimal approach(spoiler)
  1. Expand a sliding window character by character, counting letter frequencies.
  2. Track the highest single-letter count inside the window.
  3. If window length minus that count exceeds k, shrink from the left.
  4. The answer is the largest valid window length observed.
  5. O(n) time, O(1) space for a fixed alphabet.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor