## 696. Count Binary Substrings

Give a string `s`, count the number of non-empty (contiguous) 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: "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: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
```

Note:

• `s.length` will be between 1 and 50,000.
• `s` will only consist of "0" or "1" characters.

• b'
\n\n

#### Approach #1: Group By Character [Accepted]

\n

Intuition

\n

We can convert the string `s` into an array `groups` that represents the length of same-character contiguous blocks within the string. For example, if `s = "110001111000000"`, then `groups = [2, 3, 4, 6]`.

\n

For every binary string of the form `\'0\' * k + \'1\' * k` or `\'1\' * k + \'0\' * k`, the middle of this string must occur between two groups.

\n

Let\'s try to count the number of valid binary strings between `groups[i]` and `groups[i+1]`. If we have `groups[i] = 2, groups[i+1] = 3`, then it represents either `"00111"` or `"11000"`. We clearly can make `min(groups[i], groups[i+1])` valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.

\n

Algorithm

\n

Let\'s create `groups` as defined above. The first element of `s` belongs in it\'s own group. From then on, each element either doesn\'t match the previous element, so that it starts a new group of size 1; or it does match, so that the size of the most recent group increases by 1.

\n

Afterwards, we will take the sum of `min(groups[i-1], groups[i])`.

\n

Python

\n
`class Solution(object):\n    def countBinarySubstrings(self, s):\n        groups = \n        for i in xrange(1, len(s)):\n            if s[i-1] != s[i]:\n                groups.append(1)\n            else:\n                groups[-1] += 1\n\n        ans = 0\n        for i in xrange(1, len(groups)):\n            ans += min(groups[i-1], groups[i])\n        return ans\n`
\n

Alternate Implentation

\n
`class Solution(object):\n    def countBinarySubstrings(self, s):\n        groups = [len(list(v)) for _, v in itertools.groupby(s)]\n        return sum(min(a, b) for a, b in zip(groups, groups[1:]))\n`
\n

Java

\n
`class Solution {\n    public int countBinarySubstrings(String s) {\n        int[] groups = new int[s.length()];\n        int t = 0;\n        groups = 1;\n        for (int i = 1; i < s.length(); i++) {\n            if (s.charAt(i-1) != s.charAt(i)) {\n                groups[++t] = 1;\n            } else {\n                groups[t]++;\n            }\n        }\n\n        int ans = 0;\n        for (int i = 1; i <= t; i++) {\n            ans += Math.min(groups[i-1], groups[i]);\n        }\n        return ans;\n    }\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `s`. Every loop is through items with work inside the for-block.

\n
• \n
• \n

Space Complexity: , the space used by `groups`.

\n
• \n
\n
\n

#### Approach #2: Linear Scan [Accepted]

\n

Intuition and Algorithm

\n

We can amend our Approach #1 to calculate the answer on the fly. Instead of storing `groups`, we will remember only `prev = groups[-2]` and `cur = groups[-1]`. Then, the answer is the sum of `min(prev, cur)` over each different final `(prev, cur)` we see.

\n

Python

\n
`class Solution(object):\n    def countBinarySubstrings(self, s):\n        ans, prev, cur = 0, 0, 1\n        for i in xrange(1, len(s)):\n            if s[i-1] != s[i]:\n                ans += min(prev, cur)\n                prev, cur = cur, 1\n            else:\n                cur += 1\n\n        return ans + min(prev, cur)\n`
\n

Java

\n
`class Solution {\n    public int countBinarySubstrings(String s) {\n        int ans = 0, prev = 0, cur = 1;\n        for (int i = 1; i < s.length(); i++) {\n            if (s.charAt(i-1) != s.charAt(i)) {\n                ans += Math.min(prev, cur);\n                prev = cur;\n                cur = 1;\n            } else {\n                cur++;\n            }\n        }\n        return ans + Math.min(prev, cur);\n    }\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `s`. Every loop is through items with work inside the for-block.

\n
• \n
• \n

Space Complexity: , the space used by `prev`, `cur`, and `ans`.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'