Highlights
- Familiar sliding window pattern with outer for loop and inner while loop
- The usage of queue
- use current, prev & min() to keep track of previous values
Goal
- to count the number of binary substring within a string
- definition of a binary substring: 10 , 01, 0011
Strategy 1
- Outer loop used for removing the unbalance (extra) number, inner loop used for counting the number of pairs
- use a queue to store the previous characters
- why not using a stack? because we would like to identify nested substrings; in our case: ‘01’ is nested inside of ‘0011’, hence we would compare the head of the queue to the current character i
- q[-1] is the head of the queue (element inserted earlier)
- q[0] is the tail of the queue
- q.pop() is the deque action
- i==q[-1] → q=[0,1] , i = 1
- i!=q[-1] → q=[0,1], i = 0
Code 1
class Solution:
def countBinarySubstrings(self, s: str) -> int:
q = deque()
res=0 for i in s:
while q and i==q[-1] and i!=q[0]:
q.pop()
if q and i!=q[-1]:
q.pop()
res+=1
q.appendleft(i)
return res
Strategy 2
- keep track of the consecutive appearance of the same character
- once a different character is reached, use min() to find the substring: 00111 → prev =2, current = 3, min(2,3) = 2; since ‘0011’ is the binary substring of 00111
Code 2
class Solution:
def countBinarySubstrings(self, s: str) -> int:
res = 0
prev = 0
count =1
for i in range(1,len(s)):
if s[i] == s[i-1]:
count +=1
else:
res+= min(count, prev)
count, prev = 1, count
return res+min(count, prev)Time & Space
- Time: in both strategies, we traverse the string once → O(N)
- Space: in the queue approach, we are creating an extra array, but we pop() the elements out, eventually the queue is empty → O(1)
