Counting Binary Substrings Amazon OA Solution

Counting Binary Substrings Amazon OA Solution

by

Counting Binary Substrings Amazon OA Solution

Kindle Direct Publishing, Amazon’s e-book self-publishing platform, is working 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.

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’
Counting Binary Substrings Amazon OA
Counting Binary Substrings Amazon OA Solution

SOLUTION

Program: Counting Binary Substrings Amazon OA Solution in Python

Maintain Count of current & previous consecutive characters & Add minimum

The problem can be solved by observing the examples carefully

1. 0011
In this string, consecutive count of binary characters are [2, 2]. We can form a total of 2 substrings.

2. 00011
In this string, consecutive count of binary characters are [3, 2]. Still, we can only form 2 substrings.

3. 000111
Here, consecutive count of binary characters are as - [3,3]. Now, we can form 3 substrings.

4. 00011100
Consecutive count of binary characters are - [3,3,2]. We can form 3 substrings with the first 2 groups of zeros and ones. 
Then we can form 2 substrings with the latter 2 groups. So, a total of 5 substrings.

5. 00011100111
Consecutive count - [3,3,2,3]. Substrings formed - 3 + 2 + 2 = 7

We can observe from the above examples that our final count will only depend on the consecutive counts of binary characters. With each two groups of consecutive characters, the number of substrings that can be formed will be minimum of count among the two groups.

Now, although we could maintain all the groupings and their counts and then count the number of substrings, we actually don’t even need to maintain the consecutive counts in all of the string. We can just store the current consecutive count and previous consecutive count and count the substrings on the fly.

  1. s[i] == s[i - 1] : When current character is equal to previous – just increment the current consecutive count.
  2. s[i] != s[i - 1] :Whenever current character is not equal to previous – We know that we atleast have group of 2 different characters having consecutiveCount >= 1. The number of substrings that can be formed from these would be equal to minimum of currentConsecutiveCount & prevConsecutiveCount.
    So just add that amount to ans. Now prevConsecutiveCount will become equal to currentConsecutiveCount and reset the currentConsecutiveCount to 1.
def countBinarySubstrings(self, s: str) -> int:
	ans, prev, cur = 0, 0, 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			ans += min(prev, cur)
			prev = cur
			cur = 1
		else:
			cur += 1
	ans += min(prev, cur)
	return ans

Time Complexity : O(N), where N is the length of given string.
Space Complexity : O(1), since only constant space is being used.

Program: Counting Binary Substrings Amazon OA Solution in C++

int countBinarySubstrings(string& s) {
  // we start from first character - so curConsecutive = 1
  int curConsecutive = 1, prevConsecutive = 0, ans = 0;
  for(int i = 1; i < size(s); i++) {
  	if(s[i] != s[i - 1]) // whenever current & previous don't match
  		ans += min(prevConsecutive, curConsecutive), // number of substring formed is minimum of cur & prev count
  		prevConsecutive = curConsecutive,            // previous consecutive streak will become current consecutive and,
  		curConsecutive = 1;                          // current streak will be resetted
  	else 
  		curConsecutive++; 
  }
  // required to include count from last two groups of consecutive characters.
  ans += min(prevConsecutive, curConsecutive); 
  return ans;
}

Program: Counting Binary Substrings Amazon OA Solution in Java

Since the 0‘s and 1‘s have to be grouped consecutively, we only have to be concerned with the most recent two groups (curr, prev) at any time as we iterate through the input string (s). Since each addition to our answer (ans) must therefore be centered on the “edge” between the two groups, we should be able to count multiple increases to ans at the same time.

For example, if we find a group that is “0001111”, then we know that we’ve found multiple answer counts centered on the “01”. Each additional extra character on both sides will be an extra answer, which means that “0011” and “000111” are also answers. In other words, the number that we should add to ans is equal to min(zeros, ones), or 3 in this example.

So we can now iterate through s, keeping track of the curr and prev groups, and when we find the end of a group, we can calculate our addition to ans and then swap the two variables while resetting curr to 1.

Since we’re going to be comparing s[i] to s[i-1] to see if the character has changed, we’ll need to start our iteration with i = 1 which means we should define a starting value for curr of 1. Also, since the end of s is technically the end of a group, we should add another min(curr, prev) onto ans before we return ans, as it won’t be accounted for in the iteration through s.

  • Time Complexity: O(N) where N is the length of s
  • Space Complexity: O(1)
class Solution {
    public int countBinarySubstrings(String s) {
        int curr = 1, prev = 0, ans = 0;
        for (int i = 1; i < s.length(); i++)
            if (s.charAt(i) == s.charAt(i-1)) curr++;
            else {
                ans += Math.min(curr, prev);
                prev = curr;
                curr = 1;
            }
        return ans + Math.min(curr, prev);
    }
}

Program: Counting Binary Substrings Amazon OA Solution in JavaScript

var countBinarySubstrings = function(s) {
    let curr = 1, prev = 0, ans = 0
    for (let i = 1; i < s.length; i++)
        if (s[i] === s[i-1]) curr++
        else ans += Math.min(curr, prev), prev = curr, curr = 1
    return ans + Math.min(curr, prev)
};

Amazon Online Assessment Questions:

Leave a Comment

6 − four =