DSA Longest Repeating Character Replacement

The problem

Longest Repeating Character Replacement finds the longest stretch of a text that can turn into one repeated letter with at most k changes. A change replaces one letter inside the stretch with another letter.

The answer is a length, not the stretch itself. Every letter in the final stretch must end up the same. The budget k may be zero, and the text may be empty.

cases = [
    ("AABABBA", 1, 4),
    ("AABABBA", 2, 5),
    ("ABAB", 2, 4),
    ("AAAA", 0, 4),
    ("ABCDE", 0, 1),
]
for text, k, expected in cases:
    print("text", text, "k", k, "longest:", expected)

Read one row at a time. The first text answers 4 with one change and 5 with two changes. The last row allows no changes, so only a plain run of one letter counts, and its longest run has length 1.

Intuition: the longest plain run is not the answer

The first idea looks for the longest run of one letter already in place. That run needs no changes at all. It feels like the natural starting point.

The run misses the point of the budget. One change can join two groups of the same letter across a single different letter. The joined stretch beats every plain run in the text below.

text = "AABABBA"
best_run = 1
run = 1
for i in range(1, len(text)):
    if text[i] == text[i - 1]:
        run += 1
    else:
        run = 1
    best_run = max(best_run, run)
window = text[0:4]
counts = {}
for ch in window:
    counts[ch] = counts.get(ch, 0) + 1
top = max(counts.values())
print("longest plain run:", best_run)
print("window:", window, "changes needed:", len(window) - top)

The plain run stops at 2. The window AABA needs one change and reaches length 4. Scattered copies of one letter are worth more than one solid block.

Brute force: price every stretch

The brute force tests every start and every end. For each stretch it counts the letters and prices the stretch. The price is the stretch length minus its highest letter count.

The highest letter count is called the majority count here, even when it is not over half. Keeping that letter is cheapest. Every other letter in the stretch must change.

def longest_brute(text, k):
    best = 0
    checked = 0
    for start in range(len(text)):
        counts = {}
        for end in range(start, len(text)):
            ch = text[end]
            counts[ch] = counts.get(ch, 0) + 1
            checked += 1
            length = end - start + 1
            if length - max(counts.values()) <= k:
                best = max(best, length)
    return best, checked

best, checked = longest_brute("AABABBA", 1)
print("longest:", best)
print("stretches priced:", checked)
best, checked = longest_brute("ABAB", 2)
print("longest:", best)
print("stretches priced:", checked)

Seven letters hold 28 stretches, and the count grows fast. Doubling the text roughly quadruples the stretch count. The brute force pays that count on every input, easy or hard.

The optimal solution: a window that only grows or slides

A sliding window keeps letter counts and the highest count, and it shrinks from the left only while its price is over budget. That one sentence is the whole method.

The price of the current window is its length minus its highest count. A price at or under k means the window is valid. The best valid length seen so far is the answer.

The highest count never needs to shrink in this method. Only a larger window can beat the best length. A smaller highest count could never unlock a longer valid window, so the stored value stays safe.

def longest_replacement(text, k):
    counts = {}
    left = 0
    best = 0
    top = 0
    for right, ch in enumerate(text):
        counts[ch] = counts.get(ch, 0) + 1
        top = max(top, counts[ch])
        while (right - left + 1) - top > k:
            counts[text[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

cases = [
    ("AABABBA", 1, 4),
    ("AABABBA", 2, 5),
    ("ABAB", 2, 4),
    ("AAAA", 0, 4),
    ("ABCDE", 0, 1),
]
for text, k, expected in cases:
    result = longest_replacement(text, k)
    print("text", text, "k", k, "->", result, "expected:", expected, "match:", result == expected)

All five cases from the start of the article pass. The same window code handles every budget. No case needs its own rule.

Walkthrough: AABABBA with k of 1

The walk grows the window one letter at a time. The state is the window, its counts, and its price. A price over 1 moves the left edge until the price fits again.

text = "AABABBA"
k = 1
counts = {}
left = 0
top = 0
best = 0
for right, ch in enumerate(text):
    counts[ch] = counts.get(ch, 0) + 1
    top = max(top, counts[ch])
    while (right - left + 1) - top > k:
        counts[text[left]] -= 1
        left += 1
    best = max(best, right - left + 1)
    window = text[left:right + 1]
    print("window", window, "- counts:", sorted(counts.items()), "- price:", len(window) - top, "- best:", best)

The window reaches AABA at step four and keeps length 4 to the end. Later letters force the left edge forward, but no later window beats 4. The best value is read straight off the last line.

Complexity

The brute force prices every stretch, and a text of length n holds about n squared divided by 2 stretches, so its time is O(n squared) or worse once counting is paid. The sliding window moves each edge across the text at most once, so its time is O(n).

The brute force stores counts for one stretch at a time, so its extra space is O(1) beyond a small letter table. The window stores one count per distinct letter, so its space is O(1) for a fixed alphabet and O(distinct letters) in general.

def brute_checks(n):
    return n * (n + 1) // 2

for n in [7, 14, 28]:
    print("length", n, "- brute stretches:", brute_checks(n), " window edge moves at most:", 2 * n)

Counts beat clocks here. At 28 letters the brute force prices 406 stretches. The window's two edges together move at most 56 steps.

Edge cases and pitfalls

A budget of zero reduces the problem to the longest plain run. The same code handles it, because any mixed window has a price above zero. No special case is needed.

Recomputing the highest count after every shrink is the classic wasted step. It stays correct, but it throws away the saving that makes the method fast. The stored highest count only ever rises.

def longest_replacement(text, k):
    counts = {}
    left = 0
    best = 0
    top = 0
    for right, ch in enumerate(text):
        counts[ch] = counts.get(ch, 0) + 1
        top = max(top, counts[ch])
        while (right - left + 1) - top > k:
            counts[text[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print("empty text:", longest_replacement("", 2))
print("single letter:", longest_replacement("Z", 0))
print("budget covers all:", longest_replacement("ABAB", 4))
print("no changes allowed:", longest_replacement("ABBA", 0))
print("budget larger than text:", longest_replacement("ABC", 9))

The empty row answers 0 because the loop never runs and the best starts at 0. A budget larger than the text is harmless. The whole text is valid, so its length is the answer.