Facebook Pixel

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 & Output
Input
s — a string representation of a binary integer
Output
the number of substrings of s that satisfy the two conditions
Example
Input
s = 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

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro