Count Binary Substrings - Practice Coding Problems

Count Binary Substrings - Problem

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: In string "00110011", valid substrings include "01", "10", "0011", "1100", etc.

Input & Output

Example 1 — Basic Pattern

$ Input: s = "00110011"

› Output: 6

💡 Note: Valid substrings: "01" (at positions 1-2 and 5-6), "10" (at positions 2-3 and 4-5), "0011" (at positions 0-3), "1100" (at positions 2-5). Total = 6 substrings.

Example 2 — Alternating Pattern

$ Input: s = "10101"

› Output: 4

💡 Note: Valid substrings: "01" (at positions 1-2 and 3-4), "10" (at positions 0-1 and 2-3). Each pair of adjacent different characters forms exactly one valid substring.

Example 3 — Single Group

$ Input: s = "1111"

› Output: 0

💡 Note: No valid substrings possible since all characters are the same. We need both 0s and 1s to form valid substrings.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input String

Binary string with consecutive groups of 0s and 1s

Find Groups

Identify consecutive runs of same characters

Count Valid Substrings

Between adjacent groups, min(group1_size, group2_size) valid substrings

Key Takeaway

🎯 Key Insight: Valid substrings form only at boundaries between consecutive groups, with count = min(group_size1, group_size2)

Asked in

f Facebook 35 G Google 28 M Microsoft 22

The key insight is that valid substrings can only be formed at boundaries between consecutive groups of 0s and 1s. For each adjacent pair of groups, the number of valid substrings equals the minimum of their lengths. The optimal single-pass approach tracks previous and current group sizes, calculating results on-the-fly. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Group Counting with Two Pointers	O(n)	O(n)	Count consecutive groups, then calculate valid pairs between adjacent groups
Brute Force	O(n³)	O(1)	Check every possible substring for valid pattern
Single Pass Optimized	O(n)	O(1)	Count groups and calculate valid substrings in one pass

Group Counting with Two Pointers — Algorithm Steps

Step 1: Count length of each consecutive group
Step 2: For each adjacent pair of groups, min(group1_length, group2_length) valid substrings
Step 3: Sum all valid substring counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Groups

Find consecutive runs of same characters

Calculate Pairs

Between each adjacent group pair, min(len1, len2) valid substrings

Sum Results

Add up all valid substring counts

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(const char* s) {
    int len = strlen(s);
    if (len == 0) return 0;
    
    // First pass: count consecutive groups
    int groups[1000];
    int groupCount = 0;
    int currentCount = 1;
    
    for (int i = 1; i < len; i++) {
        if (s[i] == s[i-1]) {
            currentCount++;
        } else {
            groups[groupCount++] = currentCount;
            currentCount = 1;
        }
    }
    groups[groupCount++] = currentCount;
    
    // Second pass: count valid substrings between adjacent groups
    int result = 0;
    for (int i = 0; i < groupCount - 1; i++) {
        result += min(groups[i], groups[i+1]);
    }
    
    return result;
}

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through string: O(n) to count groups + O(k) to process groups where k ≤ n

✓ Linear Growth

Space Complexity

O(n)

Array to store group lengths, worst case O(n) groups for alternating string

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Group Counting with Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler