Balanced bits
The longest stretch with as many 0s as 1s. About 12 minutes.
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.
- best
- 0
- first
- {0: start, -1: 0}
- balance
- -1
Keep a running balance, starting from 0 before the list. The first 0 takes it to -1. Write down where each balance first appeared.
A stretch has as many 0s as 1s. If every 0 counts as −1 and every 1 as +1, what does the stretch add up to?
- A0
- BHalf its length
- C1
Show the answer
0. Equal numbers of −1s and +1s cancel out.
Balanced bits
You get a list of bits (0s and 1s). Return the length of the longest run of consecutive bits containing as many 0s as 1s, or 0 if there is none.
bits = [0, 0, 1, 0, 0, 0, 1, 1] → 6
0 ≤ n ≤ 1,000,000