Skip to content

Volume ITechnology

4.6.3 — Longest Repeating Character Replacement ​

LeetCode 424 · Medium · ★ Blind 75

The problem ​

You are given a string s of uppercase English letters and a number k. You may change up to k characters in the string, each to any other uppercase letter. Return the length of the longest stretch of the string that you can turn into one letter repeated.

s = "ABAB",    k = 2   →  4    (change both A's to B: "BBBB")
s = "AABABBA", k = 1   →  4    (take "AABA" and change the B: "AAAA")

The string has up to 100,000 letters, and k is between 0 and the string's length.

What the problem is really asking ​

Take any stretch of the string. How many changes does it need to become one repeated letter?

The cheapest plan is always the same. Keep the letter that already appears most often in the stretch, and change every other letter to it. So if the stretch has length L, and its most common letter appears \text{maxCount} times, it needs:

\text{changes needed} = L - \text{maxCount}

Read it as "the length of the stretch, minus how many times its most common letter appears". For "AABA", L = 4 and A appears 3 times, so it needs 4 - 3 = 1 change.

So the real question is: what is the longest stretch where L - \text{maxCount} \le k? That is a sliding window with a condition, exactly like 4.6.2.

Think of a group of children who must all wear the same colour of shirt, and you can afford k new shirts. In a group where 5 wear red, 2 wear blue and 1 wears green, you keep red and buy 3 red shirts. If you can only afford 2, this group is too big. Someone has to leave the group, from the left end, until the shirts you need fit your budget.

The brute force, and where it wastes work ​

Try every stretch, count its letters, and check the condition.

python
def characterReplacement(s, k):
    best = 0
    n = len(s)
    for i in range(n):
        count = [0] * 26
        for j in range(i, n):
            count[ord(s[j]) - ord('A')] += 1
            if (j - i + 1) - max(count) <= k:
                best = max(best, j - i + 1)
    return best

This is O(n^2 \cdot 26), far too slow for 100,000 letters.

The waste in one sentence: every time the start i moves by one, the brute force recounts a stretch that differs from the previous one by a single letter.

The idea ​

Use a sliding window with a count of each letter inside it.

  1. Move the right edge forward and count the new letter.
  2. While the window needs more than k changes, drop the leftmost letter.
  3. Record the window's length.

The solution ​

python
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}                                            # (1)
        left = 0
        max_count = 0                                         # (2)
        best = 0

        for right in range(len(s)):                           # (3)
            count[s[right]] = count.get(s[right], 0) + 1      # (4)
            max_count = max(max_count, count[s[right]])       # (5)

            while (right - left + 1) - max_count > k:         # (6)
                count[s[left]] -= 1                           # (7)
                left += 1

            best = max(best, right - left + 1)                # (8)

        return best
ts
function characterReplacement(s: string, k: number): number {
  const count = new Map<string, number>();                    // (1)
  let left = 0;
  let maxCount = 0;                                           // (2)
  let best = 0;

  for (let right = 0; right < s.length; right++) {            // (3)
    const c = s[right];
    count.set(c, (count.get(c) ?? 0) + 1);                    // (4)
    maxCount = Math.max(maxCount, count.get(c)!);             // (5)

    while ((right - left + 1) - maxCount > k) {               // (6)
      count.set(s[left], count.get(s[left])! - 1);            // (7)
      left++;
    }

    best = Math.max(best, right - left + 1);                  // (8)
  }

  return best;
}

Line by line ​

(1) count = {}. How many times each letter appears inside the window.

(2) max_count = 0. The biggest count of any one letter we have seen in a window. Read the section after this one carefully, because this number behaves in a surprising way.

(3) Move the right edge forward, one letter per turn.

(4) Count the new letter. count.get(s[right], 0) means "the current count, or 0 if this letter is not in the map yet". Then we add 1.

(5) Update max_count. Only the letter that just arrived could have a new, bigger count, so we only need to compare with that one.

(6) Does the window need too many changes? right - left + 1 is the window's length L. L - max_count is the number of changes needed. If that is more than k, the window is not allowed.

(7) Shrink from the left. The leftmost letter leaves the window, so its count drops by one, and left moves forward.

(8) Record the length. After the repair, the window is allowed, so its length is a candidate answer.

The line that looks like a bug ​

Look at line (7). When a letter leaves the window, its count goes down. But max_count is never lowered. So after shrinking, max_count may be bigger than the real top count in the window. The code carries an out-of-date number on purpose. Surprisingly, the answer is still correct. Here is why.

  1. The answer best only grows when we find a window longer than every window before it.
  2. A longer allowed window needs L - \text{maxCount} \le k with a bigger L. With k fixed, a bigger L needs a bigger maxCount than any window before.
  3. Now suppose max_count is out of date and too big. Then the check in line (6) is too gentle, and a window may stay larger than it should. But that window is never longer than best already is, because max_count was reached by an earlier window, and best already counted that window's length. So best does not wrongly grow.
  4. The moment a truly better window appears, its top letter really does reach a bigger count. Line (5) updates max_count to that real value, and best grows correctly.

So the stale number can only fail to shrink windows that could never have beaten the answer anyway. Two things follow from this.

  • The window never becomes shorter than the best length found so far. It slides along the string like a ruler, sometimes growing, never shrinking below the record.
  • The value in max_count is not always the true top count of the current window. It is a "highest so far" mark. That is fine here, but it would be wrong if the problem asked you to report the top count.

If this feels uneasy, there is an honest version. Recompute the true top count inside the while condition with max(count.values()). That scans at most 26 letters each time, so it is still O(26n) = O(n), and it is easier to defend. Many strong candidates write that version on purpose.

Trace ​

Take s = "AABABBA" and k = 1.

rightLetterWindowCountsmax_countChanges neededActionbest
0AAA:110keep1
1AAAA:220keep2
2BAABA:2, B:121keep3
3AAABAA:3, B:131keep4
4BAABABA:3, B:232 > 1drop A → ABAB4
5BABABBA:2, B:332 > 1drop A → BABB4
6ABABBAA:2, B:332 > 1drop B → ABBA4

The answer is 4. Notice that the window length stays at 4 from step 3 onward. It slides, but never shrinks below the record. That is the ruler behaviour described above.

Complexity, derived ​

Time. right moves forward n times. left only moves forward and never passes right, so it moves at most n times in total over the whole run. Each move does constant work on the map. So the total is O(n), even though there is a while inside the for.

Space. The map holds at most 26 letters. That is a fixed size, so the space is O(1).

Edge cases ​

  • k is at least the string length, like "AB" with k = 2. You can change everything, so the answer is the whole length.
  • k = 0. No changes allowed. The problem becomes "the longest run of one repeated letter", and the code handles it unchanged.
  • One letter repeated, like "AAAA". Changes needed is always 0, and the window grows to the end.

Variations you will meet ​

This is the "at most k of something" window, one of the two most common window conditions.

  • Max Consecutive Ones III. A list of 0s and 1s. You may flip up to k zeros. Find the longest run of 1s. Shrink while the window holds more than k zeros. That problem is this one with only two letters, which is a good test of whether you understood this page.
  • Longest substring with at most k different characters. Shrink while the map has more than k keys.
  • Longest stretch with sum at most k, when all numbers are zero or more. Shrink while the sum is too big.

That last one comes with a condition you must check before using any window: shrinking must always make the window closer to allowed. With numbers that are zero or more, removing a number can never raise the sum, so shrinking always helps. If negative numbers are allowed, removing one raises the sum, and the window method breaks. Then you need running totals with a hash map instead.

What the interviewer will push on ​

"Why is the condition length - maxCount <= k?" Keep the most common letter and change the rest. Keeping any other letter would mean changing more.

"You never lower max_count. Is that a bug?" This is the question this problem exists to ask. Give the argument above: a stale value can only fail to shrink a window that could never beat the answer.

"What if the string could hold any character, not just 26 letters?" The map still works. Only the space changes, to O(m) for m different characters.

"What if you had to return the actual stretch?" Save left whenever best grows, then slice at the end.

One thing to volunteer: mention that this is Max Consecutive Ones III with a 26-letter alphabet. Seeing that two problems that look different are the same is a strong signal.

Next: 4.6.4 Permutation in String. A window of fixed size, which changes the shape of the loop.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet