Greedy Window Expansion (Expanding Range While Valid)

Greedy expansion keeps stretching R while the window stays valid or profitable, only retreating from L when necessary. It is the optimistic “take more until you can’t” strategy.

Why this shows up in the real world

Delivery route packing might greedily add the next parcel while the truck capacity predicate holds. Streaming feature flags enable experiments for all users until error rate crosses a threshold—then shrink eligibility.

Core idea (explained for students)

Often paired with monotonic validity: expand R, while invalid shrink L. The greedy choice is to always try the longest valid window ending at R when maximizing length.

Try this in Python

def longest_unique_substring(s: str) -> int:
    seen, L, best = {}, 0, 0
    for R, ch in enumerate(s):
        if ch in seen and seen[ch] >= L:
            L = seen[ch] + 1
        seen[ch] = R
        best = max(best, R - L + 1)
    return best


print(longest_unique_substring("abcabcbb"))

Common mistakes

• Greedy fails when the optimal window is not discoverable by local expansion—always sketch a counterexample.
• Stalling L when multiple distinct shrink steps are needed.

Key takeaways

• Expansion/shrink loops are templates—memorize the skeleton, customize the predicate.