← all entries
A-017● Day 172026.05.19mediumleetcode #424neetcode150

Longest Repeating Character Replacement

#hash-table#string#sliding-window
↗ leetcode #424 · longest-repeating-character-replacement
01

Problem

· problem
P.017

Longest Repeating Character Replacement

↗ leetcode #424

You are given a string s and an integer 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. Return the length of the longest substring containing the same letter you can get after performing the above operations.

constraints
  • · 1 ≤ s.length ≤ 10^5
  • · s consists of only uppercase English letters
  • · 0 ≤ k ≤ s.length
// paraphrased summary — see source for full text
examples
example 1input → output
"ABAB"
2
4
example 2input → output
"AABABBA"
1
4
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What happens when k=0 (no changes allowed)?
  • ☐
    Must the substring be contiguous?
  • ☐
    To minimize changes, which character should we change all others to?
  • ☐
    Must we use exactly k changes?
  • ☐
    Is the window size fixed?
  • ☐
    Do we actually modify the string?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize character frequency map
○
count = {}
○
count = []
○
count = set()
step 2· Initialize left pointer
○
l = 0
○
l = -1
○
l = r
step 3· Initialize max frequency tracker
○
maxf = 0
○
maxf = 1
step 4· Expand window with right pointer│ nested
○
for r in range(len(s)):
○
for r in range(1, len(s)):
step 5· Increment character count│ │ nested
○
count[s[r]] = 1 + count.get(s[r], 0)
○
count[s[r]] += 1
○
count[s[r]] = count[s[r]] + 1
step 6· Update maximum frequency│ │ nested
○
maxf = max(maxf, count[s[r]])
○
maxf = max(maxf, max(count.values()))
step 7· Check if window is valid│ │ nested
○
if (r - l + 1) - maxf > k:
○
if (r - l + 1) - maxf >= k:
○
if (r - l) - maxf > k:
step 8· Remove left character and move pointer│ │ │ nested
○
count[s[l]] -= 1
○
del count[s[l]]
○
count[s[l]] = 0
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def characterReplacement(self, s: str, k: int) -> int:
3
        count = {}
4
5
        l = 0
6
        maxf = 0
7
        for r in range(len(s)):
8
            count[s[r]] = 1 + count.get(s[r], 0)
9
            maxf = max(maxf, count[s[r]])
10
11
            if (r - l + 1) - maxf > k:
12
                count[s[l]] -= 1
13
                l += 1
14
15
        return (r - l + 1)
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
"ABAB"
2
→
4
case 2
"AABABBA"
1
→
4
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.