Count Binary Substrings

Share

Count substrings with equal number of consecutive 0s and 1s (like "0011","10","01","1100").

Example 1
Input: s="00110011" → Output: 6
Example 2
Input: s="10101" → Output: 4

Solution Approach

Track previous group size and current group size. When group changes, pairs available = min(prev, curr).

  • Track prev (previous group length) and curr (current group length)
  • When character changes: add min(prev,curr) to count, prev=curr, curr=1
  • Otherwise curr++
  • Return count
Java
public int countBinarySubstrings(String s) {
    int prev = 0, curr = 1, count = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i-1)) curr++;
        else { prev = curr; curr = 1; }
        if (prev >= curr) count++;
    }
    return count;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)