Faangprep Logo
LoginRegister
Sliding Window
Medium

Longest Repeating Character Replacement

Replace characters to get the longest repeating character substring.
10 min read
Solve on LeetCode
Examples
Input:s = "ABAB", k = 2
Output:4
Explain:

Replace the two 'A's with two 'B's or vice versa to get "AAAA" or "BBBB".

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

Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has length 4.

Problem Understanding

You are given a string s and a number 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.

Goal: key is to find the length of the longest substring containing the same letter you can get after performing the above operations.

Algorithm Strategy

We use a Sliding Window to check if a valid window exists. A window (substring) is valid if we can turn it into all same characters using at most k replacements.

Logic:

  1. Validity Check: Replacements Needed = Window Length - Count of Most Frequent Char.
    • If Replacements Needed <= k, the window is valid. We try to expand it (increment right).
    • If Replacements Needed > k, the window involves too many changes. We perform one shrink step (increment left) to try and make it valid again.
  2. We maintain a frequency map (or array of size 26) to track counts of characters in the current window.
  3. We keep track of max_count, which is the count of the most frequent character inside our current window. This avoids re-scanning the map every time.
Interactive Visualization
Step 1 / 1

Initializing...

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep