Swift Leetcode Series: Count Binary Substrings

April Leetcode Challenge: Day 23 in Swift

You can also read the full story along with other interesting ones on TheSwiftNerd blog with the link above.

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.

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.

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)

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github

Senior iOS Engineer. Writer at https://theswiftnerd.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store