Page Contents
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:
- The 0s and 1s are grouped consecutively (e.g., 01, 10, 0011, 1100, 000111, etc.).
- 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’

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.
s[i] == s[i - 1]
: When current character is equal to previous – just increment the current consecutive count.s[i] != s[i - 1]
:Whenever current character is not equal to previous – We know that we atleast have group of 2 different characters havingconsecutiveCount >= 1
. The number of substrings that can be formed from these would be equal to minimum ofcurrentConsecutiveCount
&prevConsecutiveCount
.
So just add that amount toans
. NowprevConsecutiveCount
will become equal tocurrentConsecutiveCount
and reset thecurrentConsecutiveCount
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:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution