Back to problems

Count substrings and generate TOC

Algorithm · JPMorgan · Hard

Given a binary string s (only the characters '0' and '1'), count the non-empty contiguous substrings that satisfy both of the following: The substring contains an equal number of 0s and 1s. All 0s in the substring form a single consecutive block, and all 1s in the substring form a single consecutive block. Equivalently, a valid substring is made of exactly two adjacent runs of equal length: one run of 0s and one run of 1s, in either order (for example, "0011", "1100", "01",…

Checking your access…