Swift Leetcode Series: Count Binary Substrings
April Leetcode Challenge: Day 23 in Swift
Count Binary Substrings -
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and…
You can also read the full story along with other interesting ones on TheSwiftNerd blog with the link above.
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.
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.
Input: “10101” Output: 4 Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.
s.lengthwill be between 1 and 50,000.
swill only consist of “0” or “1” characters.
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.
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)