Amazon Online Assessment 2021 (OA) - Counting Binary Substrings

In the vibrant world of self-publishing digital books, there's an intriguing new feature being developed that will help authors explore the usage of strings of text in various ways. Focusing on substrings, these are clusters of characters that are continuously found within a string; to illustrate, all the substrings of abc would be [a, b, c, ab, bc, abc].

Another interesting task to grapple with involves binary numbers, which are numbers represented only by 0s and 1s. The challenge is to determine the total count of substrings that comply with two specific rules:

  1. The 0s and 1s must be grouped together, meaning they should appear side by side. This could look something like 01, 10, 0011, 1100, 000111, and so forth.

  2. The number of 0s and the number of 1s in the substring must be equal; if there are two 0s, there should also be two 1s, and so on.

Relevant Amazon OA Problems:

Input

  • s: a string representation of a binary integer

Output

the number of substrings of s that satisfy the two conditions

Examples

Example 1:

Input:

1s = 001101

Output: 4

Explanation:

The 4 substrings matching the two conditions include [0011, 01, 10, 01]. Note that 01 appears twice, from indices 1-2 and 4-5. There are other substrings, e.g. 001 and 011 that match the first condition but not the second.

Constraints

  • 5<=|s|<=5*10^5
  • each s[i] is either '0' or '1'

Try it yourself

Solution

←
↑TA 👨‍🏫