Goal: The longest stretch with as many 0s as 1s.
No label this time
From here on, the steps don't tell you which idea to use. That's what real interviews and real work feel like: a problem arrives without a label.
So before you code, ask yourself three things. What am I counting or comparing? Can I turn the question into one about totals, pairs or windows? And which tool from this topic answers that quickly? A small hint for this one: try giving the 0s and the 1s different signs.
Before coding: what am I counting, and which tool fits?
bits = [1, 1, 0, 1, 0, 0, 0, 1] · a 0 counts -1, a 1 counts +1
1
01
10
21
30
40
50
61
7i
- best
- 0
- first
- {0: start, 1: 0}
- balance
- 1
Keep a running balance, starting from 0 before the list. The first 1 takes it to +1. Write down where each balance first appeared.
Move 1 of 6