Count Binary Substrings

Leetcode 696

Difficulty : Easy Link: Leetcode April Challenge 2021: Day 23

Problem Description

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: “10101” Output: 4 Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.

Constraints

  • s.length will be between 1 and 50,000.
  • s will only consist of “0” or “1” characters.

Solution

The problem is of Easy difficulty but the right approach can be tricky to get so first let us try to first develop the intuition about the approach.

Since the input is a binary string and we are only interested in the consecutive lengths, clearly “0”s and “1”s forms bands or strips of regions of same characters.

Binary String bands

We can group these consecutive bands on the basis of lengths then the representation for above input can be visualised as [2, 7 ,3 ,1]. Any consecutive bands mean that they are different digits, otherwise it would be count in only one band (Makes Sense ?). Also, when we compare consecutive bands like 2,7 . The number of substrings that can be formed is the minimum of both bands. For example, the string is “00111”, the bands would be [2,3] and minimum (2,3) = 2 ( “01”, “0011”). Also the bands could represent either 0 or 1 substring it doesn’t matters. So [2,3] can represent “00111” or “11000” both but the answer would always be same i.e, min(2,3).

If you are able the get the above intuition, then all that is left is to iterate over the string input and count the previous running lengths and current running lengths. If the current element is same as previous element when we can increase the current length. If they do not match, then the previous band becomes the current one and current becomes 1 due to the current character.

Code

Swift

class Solution {
func countBinarySubstrings(_ s: String) -> Int {
let array = Array(s)
var current = 1, prev = 0, substringCount = 0
for i in 1..<s.count {
if array[i] == array[i 1] {
current += 1
}
else{
substringCount += min(current,prev)
prev = current
current = 1
}
}
return substringCount + min(current,prev)
}
}

Java

class Solution {
public int countBinarySubstrings(String s) {
int ans = 0, prev = 0, cur = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i1) != s.charAt(i)) {
ans += Math.min(prev, cur);
prev = cur;
cur = 1;
} else {
cur++;
}
}
return ans + Math.min(prev, cur);
}
}

Python

class Solution(object):
def countBinarySubstrings(self, s):
ans, prev, cur = 0, 0, 1
for i in xrange(1, len(s)):
if s[i1] != s[i]:
ans += min(prev, cur)
prev, cur = cur, 1
else:
cur += 1
return ans + min(prev, cur)

Complexity Analysis

We are iterating through the string input once to process every element. We are some integer variable to keep total count and running lengths so space is constant.

Time = O(N)

Space = O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *