696. Count Binary Substrings

Time: O(n)

Space: O(1)

Intuition

Count substrings with equal consecutive 0s and 1s. Group consecutive same characters. For adjacent groups of sizes a and b, min(a,b) valid substrings.

Algorithm

1Group characters into run-length encoding (consecutive same chars).
2For each pair of adjacent groups with sizes a and b: add min(a,b) to answer.

Example Walkthrough

Input: "00110011"

1.Groups: [2,2,2,2]. Adjacent pairs: min(2,2)=2 each. Total=6.

Output: 6

Common Pitfalls

•Only need to track previous group size, not all groups.

696.cs

// Approach: Track previous and current group lengths; at each group boundary,
// add min(prev, curr) valid substrings to the answer.
// Time: O(n) Space: O(1)

public class Solution
{
    public int CountBinarySubstrings(string s)
    {
        int ans = 0;
        int prevEquals = 0;
        int currEquals = 1;

        for (int i = 0; i + 1 < s.Length; ++i)
        {
            if (s[i] == s[i + 1])
                ++currEquals;
            else
            {
                ans += Math.Min(prevEquals, currEquals);
                prevEquals = currEquals;
                currEquals = 1;
            }
        }

        return ans + Math.Min(prevEquals, currEquals);
    }
}

Was this solution helpful?