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:

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

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions

Upgrade