Amazon Online Assessment 2021 (OA) - Counting Binary Substrings

Kindle Direct Publishing, Amazon's e-book self-publishing platform, isworking on a new feature to help authors track the use of text strings in different ways. A substring is a group of contiguous characters in a string. For instance, all substring of abc are [a, b, c, ab, bc, abc].

Given a binary representation of a number, determine the total number of substring present that match the following conditions:

1. The 0s and 1s are grouped consecutively (e.g., 01, 10, 0011, 1100, 000111, etc.).
2. The number of 0s in the substring is equal to the number of 1s in the substring.

Relevant Amazon OA Problems:

• Shipment Imbalance
• Simple Cipher
• Decode String Frequency
• Grid Connections
• Class Grouping

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