Problem statement

https://leetcode.com/problems/count-binary-substrings/

Solution

It is easier to understand solution on some example, imagine we have 00001101111000. Then we need to look at groups of 0 and 1 which are located side by side. For example first groups we haver are 0000 and 11. It means, that we can have either 01 or 0011 as good substrings. Then we have 11 and 0, here we can take only 10. Then we have 01111, we can take 01 and finally we have 1111000 and we can take 10, 1100, 111000.

Complexity

Time complexity is O(n), space complexity is also potentially O(n), because we use len(list(j)), if you know how to avoid this, still using groupby, please let me know.

Code

class Solution:
    def countBinarySubstrings(self, s):
        t = [len(list(j)) for i, j in groupby(s)]
        return sum([min(t[i],t[i+1]) for i in range(len(t)-1)])