Variable Window Example: The Shortest Stretch of a Timetable Served by Every Route

Departures are tagged with their route: find the fewest consecutive departures that include every route at least once.

A variable window with a map of counts and a count of what is present knows in O(1) whether it holds everything it needs. A bus station's departures run on routes A B A C B B A C in that order, and a passenger who wants to see every route leave wants the fewest consecutive departures that include routes A, B and C at least once each.

Nothing here is summed, but the cue is the same: the answer is a contiguous run, and taking in another departure can only move the run towards holding every route. A map counts each route inside the window, and a second number, present, counts how many routes have a count of at least 1. Checking the map for every route at each step would cost O(k) for k routes; present changes only when a count moves between 0 and 1, so the check is present == 3.

The answer is the shortest window, so the window shrinks while it is complete, recording each complete window before dropping its first departure. The trace shows the counts after each step, and the complete windows found along the way.

Counts of each route over the departures A B A C B B A C

Inputdepartures A B A C B B A C, routes A, B and C

End 0
1. Astartend
2. B
3. A
4. C
5. B
6. B
7. A
8. C
counts A1 B0 C0, present 1
End 1
1. Astart
2. Bend
3. A
4. C
5. B
6. B
7. A
8. C
counts A1 B1 C0, present 2
End 2
1. Astart
2. B
3. Aend
4. C
5. B
6. B
7. A
8. C
counts A2 B1 C0, present 2
End 3
1. A
2. B
3. Astart
4. Cend
5. B
6. B
7. A
8. C
complete at 0 to 3, then 1 to 3, length 3; dropping B leaves counts A1 B0 C1, best 3
End 4
1. A
2. B
3. A
4. Cstart
5. Bend
6. B
7. A
8. C
complete at 2 to 4, length 3, no shorter; counts A0 B1 C1, best 3
End 5
1. A
2. B
3. A
4. Cstart
5. B
6. Bend
7. A
8. C
counts A0 B2 C1, present 2, best 3
End 6
1. A
2. B
3. A
4. C
5. Bstart
6. B
7. Aend
8. C
complete at 3 to 6, length 4; counts A1 B2 C0, best 3
End 7
1. A
2. B
3. A
4. C
5. B
6. B
7. Astart
8. Cend
complete at 4 to 7, then 5 to 7, length 3; counts A1 B0 C1, best 3

ResultThe shortest stretch is 3 departures, first found at B A C.

The listing returns the shortest window's length and start, and runs it on a timetable that never serves route C.

timetable.pypy

def shortest_with_every_route(departures: list[str], routes: set[str]) -> tuple[int, int] | None:
    counts: dict[str, int] = {}
    present = start = 0
    best = None
    for end, route in enumerate(departures):
        counts[route] = counts.get(route, 0) + 1
        if route in routes and counts[route] == 1:
            present += 1
        while present == len(routes):
            if best is None or end - start + 1 < best[0]:
                best = (end - start + 1, start)
            leaving = departures[start]
            counts[leaving] -= 1
            if leaving in routes and counts[leaving] == 0:
                present -= 1
            start += 1
    return best


routes = {"A", "B", "C"}
timetable = "A B A C B B A C".split()
length, first = shortest_with_every_route(timetable, routes)
print("timetable", *timetable, f"shortest {length}:", *timetable[first:first + length])
print("timetable A B A B:", shortest_with_every_route("A B A B".split(), routes))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

timetable A B A C B B A C shortest 3: B A C
timetable A B A B: None

The pass is O(n) time for n departures and O(k) extra space for k routes. A timetable that lacks a route never becomes complete, so the function returns None. The same window finds the shortest run of a text containing every letter of a word, with a required count for each letter and present counting the letters that have reached theirs.

Sliding Window

← → move through sections and cards