Blind 75 Visualized

#17 · Sliding Window

Longest Repeating Character Replacement

Given a string of uppercase letters and an integer k, you may replace at most k characters with any letter. Return the length of the longest substring that can be turned into a single repeated letter.

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sliding window + frequency table

A window [left, right] over the string is fixable with k replacements exactly when length − (count of its most frequent letter) ≤ k: keep the commonest letter, overwrite the rest. A frequency table gives that count while the window slides.

Memory layout

A table of at most 26 counters (one per uppercase letter): a hash map or, better, a fixed 26-int array that sits in a single cache line pair.

OperationCost
add / remove one letterO(1)
read the largest countO(1) if tracked, O(26) if rescanned
whole scanO(n) time, O(26) = O(1) space

Running maximum that never decreases

Only a window with a larger most-frequent count than any seen before can beat the current best, so the stale maximum is harmless: it can only make the window slide, never grow wrongly.

Memory layout

One integer next to the table.

OperationCost
updateO(1)

Why it fits

  • The validity test (length − maxFrequency ≤ k) depends only on the window's letter counts, which can be updated in O(1) when one letter enters and one leaves.
  • Validity is monotone: if a window is valid then every sub-window is too, so a two-pointer window never has to move left backwards.
  • The answer is the largest valid window length, so we never need to know WHICH letters get replaced: only how many.

Why alternatives degrade

Try every substring and test it:
O(n²) substrings, each needing a frequency count: O(n²) at best and O(n³) if counted naively.
Fix a target letter and DP over positions:
Works (26 passes of a window), but multiplies the work by the alphabet size and is no simpler than one counting window.
Greedy replace without a window:
The best substring can start anywhere; without window boundaries there is no way to know which letters are cheapest to replace.

Four approaches, from naive to production

1 · beginner

Grow a window from every start

time O(n²)space O(1)

For each start index, extend the end while (length − commonest letter count) ≤ k; remember the longest window that stayed within budget.

int characterReplacement(string s, int k) {
    int best = 0;
    for (int start = 0; start < (int)s.size(); start++) {
        unordered_map<char, int> count;
        int maxCount = 0;
        for (int end = start; end < (int)s.size(); end++) {
            count[s[end]]++;
            maxCount = max(maxCount, count[s[end]]);
            if (end - start + 1 - maxCount > k) break;
            best = max(best, end - start + 1);
        }
    }
    return best;
}

Flaws & bottlenecks

  • Restarts from scratch at every start index, throwing away all the counting work done for the previous start.
  • O(n²) time: for a string of identical letters nothing ever breaks the inner loop.
  • The count table is rebuilt on every start.

Interviewer cross-questions

Why is length − maxCount the number of replacements?

Say: Keep the most common letter and overwrite every other letter in the window to match it. Anything else would replace more letters, so this is the minimum.

Can you reuse work between different starts?

Say: Yes: when the window [start, end] is valid, moving start right by one only removes a letter, which keeps it valid. A single moving window with a left pointer reuses all the counts: that is the sliding window.

What are the edge cases?

Say: k = 0 (longest run of one letter), k ≥ n (answer n), a single character, and a string that is already one repeated letter.

2 · intermediate

Sliding window, rescan the counts

time O(26·n)space O(26)

Keep one window. After adding the right letter, shrink from the left while the window is invalid. The commonest count is found by scanning the whole table each time.

int characterReplacement(string s, int k) {
    unordered_map<char, int> count;
    auto maxCount = [&] { int m = 0; for (auto& [c, v] : count) m = max(m, v); return m; };
    int left = 0;
    int best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right]]++;
        while (right - left + 1 - maxCount() > k) {
            count[s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Flaws & bottlenecks

  • Scanning every count to find the maximum costs O(alphabet) per check, which multiplies the whole loop by up to 26.
  • The inner while loop re-scans after every single removal.
  • A hash map has more overhead than a fixed array for a 26-letter alphabet.

Interviewer cross-questions

Is it still linear with a while loop inside a for loop?

Say: Yes: left only moves right, so left and right together make at most 2n moves. The extra factor is the O(26) maximum scan, which is a constant but a noticeable one.

How could you avoid scanning for the maximum?

Say: Track the maximum as a single running variable. It can be stale after removals, but a stale value is safe: see the next approach for why.

What if the alphabet were all of Unicode?

Say: Then the O(alphabet) rescan is a real problem. A running maximum, or a max-heap / bucketed frequency structure, keeps the check at O(1) or O(log n).

3 · advanced

Running maximum, never shrink

time O(n)space O(26)

Track maxCount as the highest count ever seen. If the window is invalid, drop exactly one letter on the left (an if, not a while): the window slides but never gets smaller.

int characterReplacement(string s, int k) {
    unordered_map<char, int> count;
    int left = 0;
    int maxCount = 0;
    int best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right]]++;
        maxCount = max(maxCount, count[s[right]]);
        if (right - left + 1 - maxCount > k) {
            count[s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Flaws & bottlenecks

  • maxCount may be stale: the window can briefly be "invalid" by its true counts. The answer is still right, but the reasoning is subtle and easy to get wrong.
  • The window itself is not guaranteed to be a valid substring at the end; only its length is meaningful.
  • Still uses a hash map for a tiny fixed alphabet.

Interviewer cross-questions

Why is a stale maxCount safe?

Say: The window only grows when length − maxCount ≤ k. If maxCount is stale (too high), the window just slides instead of growing; to grow the best answer, a window needs an actual count at least as large as the old record, which updates maxCount. So the answer never exceeds what is truly achievable.

Why if instead of while?

Say: Adding one letter can break validity by at most one, so removing one letter restores it. Because the window never needs to shrink below its best size, one removal per step suffices.

How do you recover the actual substring?

Say: Record left and right whenever the window length beats best. At those moments the counts are genuinely valid, so the stored window is a real answer.

4 · expert

26-slot table, no best variable

time O(n)space O(1)

Same sliding window with a fixed int[26] indexed by letter code. Since the window never shrinks, its final size n − left is the answer, so no best variable or max() on the result is needed.

int characterReplacement(string s, int k) {
    int n = s.size();
    int count[26] = {0};
    int left = 0;
    int maxCount = 0;
    for (int right = 0; right < n; right++) {
        int c = s[right] - 'A';
        maxCount = max(maxCount, ++count[c]);
        if (right - left + 1 - maxCount > k) count[s[left++] - 'A']--;
    }
    return n - left;
}

Flaws & bottlenecks

  • Assumes uppercase A–Z, as the problem guarantees; any other character indexes outside the table (a crash or silent corruption depending on the language).
  • Returns only the length, not the substring; extra bookkeeping would be needed for the substring.
  • The decrement-while-advancing one-liner is terse: hard to read and easy to break.

Interviewer cross-questions

Why is n − left the answer?

Say: The window starts empty, grows by one for each character, and slides (keeps its size) when invalid. So its size never decreases, and its final size is the largest size reached: right − left + 1 at the last step = n − left.

How would you make it production safe?

Say: Validate the input: reject characters outside A–Z or map the string through a lookup table, and check k ≥ 0. For a larger alphabet, use a hash map or size the table to the alphabet.

Can k be larger than n?

Say: Yes. Then length − maxCount ≤ k always holds, the window never slides, and the answer is n, which the formula n − left gives with left = 0.

Synchronized code walkthrough

Showing: Grow a window from every start — shares the player above; click any step to jump.

int characterReplacement(string s, int k) {
    int best = 0;
    for (int start = 0; start < (int)s.size(); start++) {
        unordered_map<char, int> count;
        int maxCount = 0;
        for (int end = start; end < (int)s.size(); end++) {
            count[s[end]]++;
            maxCount = max(maxCount, count[s[end]]);
            if (end - start + 1 - maxCount > k) break;
            best = max(best, end - start + 1);
        }
    }
    return best;
}