Longest balanced run of ups and downs

Question

Each tick moved the price up ("U") or down ("D"). Find the length of the longest contiguous stretch of ticks containing equally many ups and downs. Return the length of the longest balanced substring. Aim for O(n).

Accepted Answer

Score each up as +1 and each down as -1. A stretch is balanced exactly when its running sum is zero, which happens when the prefix sum at its two ends is equal. To find the longest such stretch, remember the earliest index at which each prefix value first appeared; when that value recurs, the span from just after the first occurrence to now is balanced. Seed prefix 0 at index -1 so a balanced stretch starting at index zero is measured correctly. Tracing "UUDD": prefixes are 1, 2, 1, 0. The 1 recurs at index 2 (span 2), and the final 0 matches the seeded -1, giving span 3 - (-1) = 4, the answe…

Longest balanced run of ups and downs

Your answer

More Coding questions