Turnstile audit

A gate log is a string of entries and exits. Somewhere in it is the longest run the crew can certify: one that starts empty, never goes negative, ends empty.

The problem

One turnstile at a stadium writes a character per person: I inward, O outward. The night's log is that string, in order.

A run of consecutive scans is clean when every O in it pairs with an earlier I in the same run and every I is paired off by the end — the count inside the run starts at zero, never goes negative, and ends at zero. Report the length of the longest clean run.

The log is dirty in both directions: staff propping the gate leave exits with no entry, spectators leaving elsewhere leave entries with no exit. Either one breaks a run, and it is the position of the break, not the count, that fixes how long the surrounding runs are.

Input. log — a string over the two characters I and O.

Output. The length of the longest clean run, or 0 if there is none.

Example.

log = 'OIIOIO'   ->  4

The opening O can never sit inside a clean run, so it cuts the log. In what follows, one I is never paired, and the longest clean run is the last four scans, IOIO.

A second example, where the pairs are there but not together:

log = 'IOIIO'   ->  2

Both O scans are matched, so four of the five characters belong to a pair — but an unpaired I sits between them, and the longest clean run is IO.

Constraints.

• 0 <= len(log) <= 10^5
• log contains only I and O

Hints

Approach

Brute force

Take every start, extend to every end, carrying a counter: O(n²) runs at O(1) each — 10¹⁰ steps at n = 10⁵, minutes per night's log for a question asked hourly.

The insight

The length of a clean run is a distance between two positions, so the stack must hold positions of unmatched scans, not a count of matched ones.

Every scan is either matched or a wall no clean run may cross. Push the index of each I; an O pops the I it pairs with. If the stack still holds something, its top is the nearest wall to the left and everything after it is paired, so the run is i - stack[-1] long. If the pop empties the stack, this O had no partner and becomes the new wall. Seeding with -1 makes the rule uniform for runs that start at scan 0.

Algorithm

1. Start with stack = [-1] and best = 0.
2. Walk the log once with index i.
3. On I, push i.
4. On O, pop.
5. If the stack is now empty, push i — an exit with no partner is the new wall.
6. Otherwise best = max(best, i - stack[-1]).
7. Return best.

Complexity

Time O(n) — every index is pushed at most once and popped at most once. Space O(n) for the stack, which a log of all I scans fills completely.

Solution

"""Turnstile audit — longest clean run from a stack of unmatched scan positions."""


def solve(log):
    best = 0
    walls = [-1]                  # invariant: walls[-1] is the last position no clean run may cross
    for i, scan in enumerate(log):
        if scan == "I":
            walls.append(i)
        else:
            walls.pop()
            if walls:
                best = max(best, i - walls[-1])
            else:
                walls.append(i)   # this exit had no partner, so it is the new wall
    return best

TESTS = [
    (("OIIOIO",), 4),
    (("IOIIO",), 2),
    (("IIOO",), 4),
    (("IIOOIO",), 6),
    (("IOOI",), 2),
    (("IIIOO",), 4),
    (("",), 0),
    (("O",), 0),
    (("I",), 0),
    (("OOO",), 0),
    (("IIII",), 0),
]

Pitfalls

• Counting matched pairs and doubling. On IOIIO two exits are matched, which gives 4, but the answer is 2. The pairs are real; the contiguity is not.
• Starting the stack empty instead of with -1. On IIOO the final O empties the stack, leaving nothing to subtract from: the run measures 2 instead of 4, short by exactly the runs that reach scan 0.
• Matching equal running balances. Pairing positions where the count repeats ignores the never-negative rule: on IOOI it is 0 at both ends, claiming all four scans where the answer is 2.

Variants

• A related idea with no page of its own here: the same log can be measured in O(1) space by two sweeps, left to right and right to left, each discarding its tally the moment one kind of scan overtakes the other.