Skip to main content

Count Binary Substrings

LeetCode 696 | Difficulty: Easy​

Easy

Problem Description​

Given a binary string s, return the number of non-empty 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: s = "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: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Constraints:

- `1 <= s.length <= 10^5`

- `s[i]` is either `'0'` or `'1'`.

Topics: Two Pointers, String

Approach​

Direct Approach​

This problem can typically be solved with straightforward iteration or simple data structure usage. Focus on correctness first, then optimize.

When to use

Basic problems that test fundamental programming skills.

Solutions​

Solution 1: C# (Best: 80 ms)​

MetricValue
Runtime80 ms
Memory42.5 MB
Date2021-12-18
Solution
public class Solution {
    public int CountBinarySubstrings(string s) {
        int prev=0, cur = 1, count = 0;
        for(int i=1;i<s.Length;i++)
        {
            if(s[i] != s[i-1])
            {
                count+= Math.Min(prev, cur);
                prev = cur;
                cur = 1;
            }
            else
            {
                cur++;
            }
        }
        count += Math.Min(prev, cur);
        return count;
    }
}

Complexity Analysis​

ApproachTimeSpace
Two Pointers$O(n)$$O(1)$

Interview Tips​

Key Points
  • Start by clarifying edge cases: empty input, single element, all duplicates.
  • LeetCode provides 1 hint(s) for this problem — try solving without them first.
💡 Hints

Hint 1: How many valid binary substrings exist in "000111", and how many in "11100"? What about "00011100"?