424. Longest Repeating Character Replacement
This is such a beautiful sliding window problem.
I initially stuck on a O(n**2) sliding solution like
1# "AABABBA", 2
2# A
3# AAAAA
4# B
5# BBBBB
6# A
7# AAAA
8# B
9# BBB
10# A
where we start over after each try on the next different letter.
The key to this problem is to find the defining rule of this window.
1class Solution:
2 def characterReplacement(self, s: str, k: int) -> int:
3 counts = [0] * 26
4
5 def idx(c):
6 return ord(c) - ord("A")
7
8 l = 0
9 majority = 0 # number of occurance of the most common char within window
10 longest = 0
11
12 # rule: majority + k >= window_size
13
14 for r, c in enumerate(s):
15 i = idx(c)
16 counts[i] += 1
17 majority = max(majority, counts[i])
18
19 while majority + k < r - l + 1:
20 counts[idx(s[l])] -= 1
21 l += 1
22 # majority = max(counts) # why can we omit this? btw this is O(26n)
23
24 longest = max(longest, r - l + 1)
25
26 return longest
follow-up: why can we keep a stale `majority`?
We maintain window_size - majority <= k using a non-decreasing upper bound on the window’s max frequency. This can only make us shrink no more than necessary, never less than necessary in the long run; since majority only increases as r advances, any “too-large” window we kept will become legitimately valid soon (or be forced to shrink later), so the recorded longest remains correct.#Neetcode150 #Sliding-Window #Python