**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
```