Give a binary string s, return the number of non-empty 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: s = "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: s = "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Constraints:
1 <= s.length <= 10^5s[i] is either '0' or '1'.
The description was taken from https://leetcode.com/problems/count-binary-substrings/.
#O(N) Time, O(1) Space
class Solution:
def countBinarySubstrings(self, s: str) -> int:
last_bit, curr_bit = 0, 1
output = 0
for i in range(1, len(s)):
if s[i] != s[i-1]:
output += min(last_bit, curr_bit)
last_bit = curr_bit
curr_bit = 1
else:
curr_bit += 1
return output + min(last_bit, curr_bit)The problem boils down to when should we cash in these bit groups while we're counting them.
This happens whenever we have a new group that is no longer the current bit group or the last bit group because at that point the last bit group will no longer be considered for any future count.
To solve this problem, we can have two counters for the current bit group and the last bit group. Whenever we encounter a new bit group, we can increment the output by how many bits are matched up in the new bit group and the last bit group then we will exclude the last bit group from our search.
Let's start by initializing our last bit and current bit counters to zero and one.
Zero, because we have no last bit groups so far and one because we are making the first index of the string our initial current bit.
last_bit, curr_bit = 0, 1
We will also need an output counter to signify the consecutive bits that match.
output = 0
For each other bit besides the first one in the string, we will begin counting.
for i in range(1, len(s)):
If we have a new bit that is not the current bit, we can exclude the last bit group.
We first will take the minimum between the last bit and the current bit because we can only count the smaller number of bits that match.
001100
output += min(last_bit, curr_bit)
Then, we will make the last bit count the new bit count and reset the current bit count to one since we now have one current bit with the introduction of this new bit.
This will exclude the last bit group from our current count.
001100
last_bit = curr_bit
curr_bit = 1
Otherwise, we will continue incrementing the current bit group.
else:
curr_bit += 1
Once we have passed the end of the string, we will need to count the last group of matched bits.
We were doing this in the loop whenever we were certain that the last group would no longer be included in the current count and since we have no future counts, we can be sure now that the last group will no longer be included.
return output + min(last_bit, curr_bit)