# Python solution with detailed explanation

• Count Binary Substrings https://leetcode.com/problems/count-binary-substrings/description/

Encode the input and scan

• Encode "00110011" as encoding = [2,2,2,2].
• How many valid strings possible between encoding[i-1] and encoding[i]? Example between "0001111111" will be encoded as [3,7] and will result in "01", "0011", and "000111". We can see that this results in min(3,7) or 3.
• O(N) time and O(N) space.
``````class Solution:
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
encoding, prev = [], None
for ch in s:
if prev is not None and prev == ch:
encoding[-1] += 1
else:
encoding.append(1)
prev = ch
result = 0
for i in range(1, len(encoding)):
result += min(encoding[i-1], encoding[i])
return result
``````

Modify and maintain count of previos run and scan

• Instead of encoding entire array, we just need to remember the length of the previos run.
• O(N) time and O(1) space.
``````class Solution:
def get_run(self, start, s):
run = 0
ch  = s[start]
while start < len(s) and s[start] == ch:
start, run = start+1, run+1
return start, run

def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
start, prev_run, result  = 0, 0, 0
while start < len(s):
start, curr_run = self.get_run(start, s)
result += min(prev_run, curr_run)
prev_run = curr_run
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.