Longest Repeating Character Replacement

An interactive, step-by-step visualisation of Longest Repeating Character Replacement.

Category: Sliding Window
Time complexity: O(n)
Space complexity: O(Σ)

Pseudocode

expand right, track frequency of each char in window
if (windowLen - maxFreq) > k: shrink from left
track the longest valid window seen

Reference implementation

count = {}; lo = 0; max_freq = 0; best = 0
for hi, ch in enumerate(s):
    count[ch] = count.get(ch, 0) + 1
    max_freq = max(max_freq, count[ch])
    if (hi - lo + 1) - max_freq &gt; k:
        count[s[lo]] -= 1; lo += 1
    best = max(best, hi - lo + 1)

Open the interactive Longest Repeating Character Replacement visualisation →