Inspecting Three Buildings

Medium

Buildings stand along a street, and their types are written in the string street: '0' is an office, '1' is a café. An inspector wants to pick three buildings, taken in street order, so that their types alternate: no two neighbours within the chosen triple may be of the same type. In other words, only "office, café, office" and "café, office, café" are allowed. Return the number of ways to pick such a triple. Two ways differ if they pick a different set of buildings.

Example 1

street='10011' → 4

Only "café, office, café" works: building 0, then building 1 or 2, then building 3 or 4, so 2 · 2 = 4 ways. "Office, café, office" is impossible because no office comes after a café.

Example 2

street='000111' → 0

All the offices come before all the cafés, so no alternating triple exists.

Constraints

3 ≤ street.length ≤ 10⁵
street[i] is '0' or '1'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Prefix Sum

Similar problems

Hop Across Safe Tiles Medium Up and Down Orderings Hard Rugs Over White Tiles Hard Sticky Keys Hard Longest Mirror Fragment Medium

Input

street='10011'

Expected

Run checks the first 3 tests in your browser. Submit checks all 164 tests on the server, hidden ones included.