The O(n) Club: Count Binary Substrings — Or, Why Brute Force Devs Cry

The O(n) Club: Count Binary Substrings — Or, Why Brute Force Devs Cry

⚡ TL;DR

Count every spot where a run of ‘0’s is immediately followed by a run of ‘1’s (or vice versa), and both runs are the same length (or as many as the shorter run allows). Quick Java below—no substring slicing, no regrets:

// Java, O(n), one-pass
int total = 0, prev = 0, curr = 1;
for (int i = 1; i < s.length(); i++) {
    if (s.charAt(i) == s.charAt(i-1)) curr++;
    else {
        total += Math.min(prev, curr);
        prev = curr;
        curr = 1;
    }
}
total += Math.min(prev, curr);

🧠 How Devs Usually Mess This Up

If your first instinct is brute-force substring checking, you’re about to nuke your own runtime. Naive devs try every substring with equal ‘0’s and ‘1’s, which works for toddlers but not LeetCode input. Or, they forget that blockbuster requirement: ‘0’s and ‘1’s need to be clumped, not scattered like confetti at a failed launch party. Don’t optimize before you understand the grouping rule!

🔍 What’s Actually Going On

The binary string is basically a conga line of zeros and ones in costume—ordered, polite, never mixing. Count each time a flock of zeros bumps into a flock of ones (or vice versa) and tally up as many pairs as the smaller flock allows. For example: in “0011”, that’s two zeros, two ones —> min(2,2) = 2 exciting group dances: “0011” and “01”. No performance art substrings allowed.

🛠️ PseudoCode

• Start with prev = 0 (previous group length), curr = 1 (current group), and total = 0 (answer).
• From index 1, step through characters. If the char matches the one before, you’re still in the same herd: curr++.
• If not, count pairs: total += Math.min(prev, curr). Set prev = curr and reset curr = 1.
• After the last run, add one final Math.min(prev, curr)—those wallflowers count too.

int prev = 0, curr = 1, total = 0;
for (int i = 1; i < s.length(); i++) {
    if (s.charAt(i) == s.charAt(i-1)) {
        curr++;
    } else {
        total += Math.min(prev, curr);
        prev = curr;
        curr = 1;
    }
}
total += Math.min(prev, curr);

💻 The Code

public int countBinarySubstrings(String s) {
    int prev = 0, curr = 1, total = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            curr++;
        } else {
            total += Math.min(prev, curr);
            prev = curr;
            curr = 1;
        }
    }
    total += Math.min(prev, curr);
    return total;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Overlapping happens: “01” appears in several places? Count every one. No need to play favorites.
• Grouping is king: Substrings like “0101” as a whole don’t count; runs must be together, not alternating.
• Zero fun edge cases: “0000” or “111”: answer is 0. Strings of length 1? Also 0. Don’t panic.
• Time: O(n) — sweet dreams. Space: O(1) — runs in your head, not on your RAM bill.

🧠 Interviewer Brain-Tattoo

“Don’t brute force—group force. Only the block party neighbors count in this game.”