EasyCoding

Count Binary Substrings

Asked at

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Track previous and current run lengths.
02Extend the current run while bits match.
03On a change, add min(previous, current).
04Shift current into previous and reset.
05Add the final boundary contribution.

Reference answer

Group consecutive equal bits into runs. For each adjacent pair of runs with lengths a and b, exactly min(a, b) valid substrings use that boundary: choose one through min(a,b) characters from each side, yielding equal counts of zeroes and ones in contiguous groups. Scan once with previousRun and currentRun. When the bit changes, add min(previousRun, currentRun), assign previousRun = currentRun, and reset currentRun to one; after the scan add the last pair's contribution. This is simpler than enumerating substrings and makes the proof local to each boundary. Check a single-character string, all equal bits, and alternating bits. Time is O(n), space is O(1).

Then expect these follow-ups

Why does each valid substring belong to exactly one boundary?
Tests: correctness reasoning
How would you output the substrings for small inputs?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question