Reserve turnstile

A nature reserve counts visitors with one turnstile. The warden wants the longest window of the day over which the reserve ended no busier than it started.

The problem

The turnstile writes one character per minute into a log: I when someone came in during that minute, O when someone went out. Every minute carries exactly one of the two; the gate is never idle.

A stretch of minutes is level when it holds as many I minutes as O minutes, so the reserve holds the same number of people at both ends of it. Report the length of the longest level stretch, or 0 if none is level. The stretch must be contiguous, and the length is what is wanted, not the position.

Input. log — a string of I and O characters, possibly empty.

Output. An integer: the length in minutes of the longest level stretch, or 0.

Example.

log = "IIOOI"   ->  4

The first four minutes hold two I and two O. The last minute makes it three I against two O, so five is not level.

A second example, where the best stretch is the whole log and the balance dips below zero on the way:

log = "IOIOOI"  ->  6

Three of each over six minutes. Level stretches also end at minute 1 (IO) and minute 3 (IOIO); a method that overwrites where balance zero was last seen answers 2.

Constraints.

• 0 <= len(log) <= 10^5
• Every character is I or O.

Hints

Approach

Brute force

Take every start minute, walk forward, keep a tally of I minus O, and note the longest stretch that hits zero. That is n(n + 1) / 2 steps — about five billion for a 100 000-minute log.

The insight

A stretch is level exactly when the running balance at its two ends is equal, so the longest level stretch is the widest gap between two equal balances.

Write B[k] for the balance after k minutes, with B[0] = 0. Minutes i..j have I minus O equal to B[j+1] - B[i], zero precisely when the two balances match. So record the first index at which each balance occurred, and every later occurrence of that balance is one subtraction away from its longest stretch. The first index is the one to keep: starting earlier can only widen the stretch.

Algorithm

1. Set balance = 0 and first = {0: -1} — balance zero holds before minute 0.
2. Walk the log with an index i, adding 1 for I and subtracting 1 for O.
3. If balance is already a key of first, minutes first[balance] + 1 to i are level, of length i - first[balance]. Keep the largest.
4. Otherwise record first[balance] = i.
5. Return the largest length seen, or 0.

Complexity

Time O(n) — one pass, one map operation per minute. Space O(n) — the balance takes at most 2n + 1 values, each stored once.

Solution

"""Reserve turnstile — longest level stretch from a running balance and a first-seen map."""


def solve(log):
    balance = 0
    first = {0: -1}                   # balance 0 holds before minute 0
    longest = 0
    for i, mark in enumerate(log):
        balance += 1 if mark == "I" else -1
        if balance in first:
            # invariant: first[b] is the earliest index with balance b, so this
            # subtraction is the widest level stretch ending at i.
            longest = max(longest, i - first[balance])
        else:
            first[balance] = i        # never overwrite: earlier ends give longer stretches
    return longest

TESTS = [
    (("IIOOI",), 4),
    (("IOIOOI",), 6),
    (("III",), 0),
    (("",), 0),
    (("IO",), 2),
    (("OOIIOI",), 6),
    (("I",), 0),
    (("OIIIOO",), 6),
]

Pitfalls

• Overwriting the stored index when a balance recurs. On "IOIOOI" the entry for balance 0 moves to minute 3 and the answer comes back as 2, not 6.
• Leaving out the {0: -1} seed. Any level stretch that starts at minute 0 is then invisible: "IO" reports 0 instead of 2.
• Seeding with {0: 0} instead of {0: -1}. Every length comes out one short — "IO" reports 1 — because balance zero holds before minute 0.
• Scoring O as 0 rather than -1. The running total never decreases, equal totals only mean a run of O minutes, and "IIOO" reports 2.

Variants

• Rain tank swings — the same prefix map, counting occurrences instead of storing the first index.
• Clock drift readout — a first-seen map over division remainders, finding where a cycle begins.