Why it works
- Count a 1 as +1 and a 0 as -1. A stretch has as many 0s as 1s exactly when its sum is 0, that is, when the running balance is the same at both of its ends.
- The longest stretch ending at i starts right after the first index with the same balance. So first keeps only the first index of each balance and is never overwritten: at index 4 balance 1 comes back, and first[1] stays 2.
- first starts with {0: -1}, balance 0 before index 0, so a stretch from the very start is counted too, as [0, 1] and [0, 1, 1, 0] are here.
Complexity
Time O(n): one pass, and a map lookup or store takes O(1) on average. Memory O(n): the balance stays between -n and n, one first index for each.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗