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:

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.
We maintain a frequency map (or array of size 26) to track counts of characters in the current window.
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...

Custom Input

K Value

Watch how the window expands and only shrinks when the number of replacements needed exceeds k.

Previous Problem

Longest Substring Without Repeating

Next Problem

Maximum Points from Cards

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.