14. Sliding Window for Context-Window Truncation

Problem

A lab's chat assistant has a fixed context-window token budget. When a conversation grows too long to fit whole, the serving layer needs to pick the best contiguous run of messages to keep — as many consecutive messages as possible without blowing the token budget, preferring the most recent run of that length when more than one run ties, since recent turns matter most for continuing a conversation coherently.

Given each message's token count in chronological order, find the longest contiguous window of messages whose total token count fits the budget.

Source: src/14_sliding_window_context_truncation.py

def largest_context_window(token_counts: list[int], budget: int) -> tuple[int, int]:

>>> largest_context_window([50, 40, 30, 20, 10], 60)
(2, 5)
>>> largest_context_window([10, 10, 10, 10], 25)
(2, 4)

Step-by-Step Approach

1. Notice that as the window's right edge extends, its total token count only grows — and once it exceeds budget, shrinking from the left is the only way to bring it back under budget, since all token counts are non-negative. That monotonicity is what makes a two-pointer sliding window valid here.
2. Walk right across the messages one at a time, adding token_counts[right] to a running total.
3. While total > budget, shrink the window by subtracting token_counts[left] and advancing left, until the window fits again (or becomes empty).
4. After each shrink, the window [left, right] is the largest valid window ending exactly at right. Compare its length to the best seen so far.
5. Use >= (not strict >) when updating the best window on a length tie, so a later (more recent) window of the same length overwrites an earlier one — this implements the "prefer the most recent tie" rule directly.
6. Only count windows of length > 0 as valid, so a single message that alone exceeds the budget doesn't get recorded as a length-0 "window" at some nonzero position — the sentinel for "nothing fits" is always (0, 0).

The key insight is that each index enters and leaves the window at most once across the whole scan, so even though there's a nested while loop for shrinking, the total work across all shrink steps is bounded by n — giving O(n) time instead of the O(n²) an every-pair check would cost.

Reference solution

def largest_context_window(token_counts: list[int], budget: int) -> tuple[int, int]:
    # classic variable-size sliding window: O(n) time, O(1) extra space, since
    # each index enters and leaves the window at most once
    left = 0
    total = 0
    best_len = 0
    best = (0, 0)
    for right, count in enumerate(token_counts):
        total += count
        # shrink from the left while over budget -- total only ever grows by
        # one element per outer step, so this inner loop is amortized O(1)
        while total > budget:
            total -= token_counts[left]
            left += 1
        window_len = right - left + 1
        # ">=" (not ">") means a later tie overwrites an earlier one, so the
        # most-recent window of the max length wins
        if window_len > 0 and window_len >= best_len:
            best_len = window_len
            best = (left, right + 1)
    return best

Key Functions & Tricks

• two-pointer left/right — both pointers only ever move forward, which is what bounds the total work to O(n).
• while total > budget — shrinks from the left until the invariant ("current window fits") is restored before evaluating its length.
• window_len >= best_len — the tie-break rule that makes later, more-recent windows win over earlier ones of equal length.
• enumerate(token_counts) — supplies the right-pointer index alongside each value without a manual counter.
• window_len > 0 guard — keeps a degenerate empty window from being recorded as a real result at a nonzero position.

How to Recognize This Pattern