Formatted question description: https://leetcode.ca/all/696.html
696. Count Binary Substrings
Level
Easy
Description
Give a string s
, count the number of nonempty (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.
Solution
First find the indices where the character is different to its next character.
Next, for each index found, use two pointers to point to the left index and the right index. While characters in the left half of the substring are consecutive 0’s and characters in the right half of the substring are consecutive 1’s, or characters in the left half of the substring are consecutive 1’s and characters in the right half of the substring are consecutive 0’s, move both pointers toward the ends of the string by 1 step, and count the number of binary substrings.
Finally, return the number of binary substrings.
Java

class Solution { public int countBinarySubstrings(String s) { int count = 0; int length = s.length(); List<Integer> indices = new ArrayList<Integer>(); for (int i = 0; i < length  1; i++) { if (s.charAt(i) != s.charAt(i + 1)) indices.add(i); } for (int index : indices) { int indexLeft = index, indexRight = index + 1; char charLeft = s.charAt(indexLeft), charRight = s.charAt(indexRight); while (indexLeft >= 0 && indexRight < length) { if (s.charAt(indexLeft) != charLeft  s.charAt(indexRight) != charRight) break; count++; indexLeft; indexRight++; } } return count; } }

// OJ: https://leetcode.com/problems/countbinarysubstrings/ // Time: O(N) // Space: O(1) class Solution { public: int countBinarySubstrings(string s) { int prev = 0, N = s.size(), ans = 0; for (int i = 0; i < N; ) { int j = i++; while (i < N && s[i] == s[i  1]) ++i; int cnt = i  j; ans += min(cnt, prev); prev = cnt; } return ans; } };

class Solution(object): def countBinarySubstrings(self, s): """ :type s: str :rtype: int """ N = len(s) res = 0 for i in range(N): c1, c0 = 0, 0 if s[i] == "1": c1 = 1 else: c0 = 1 for j in range(i + 1, N): if s[j] == "1": c1 += 1 else: c0 += 1 if c0 == c1: res += 1 break return res