Find All 0(1+)0 Patterns in a String: C & Python Guide

Counting all 0(1+)0 occurrences in a binary string is a standard problem in placement coding rounds. The pattern definition looks straightforward; the overlapping-match rule and the missing-guard cases are where most implementations break.

What the 0(1+)0 Pattern Means

The notation 0(1+)0 borrows from regular expression syntax. In plain terms, you are looking for any substring that:

• starts with the character 0
• contains one or more consecutive 1s
• ends with the character 0

Valid matches: 010, 0110, 01110, 011110 (any number of 1s qualifies, as long as the count is at least 1). Invalid: 00 (no 1 in between), 01 (no closing 0), 1010 (does not start with 0).

Three worked examples fix the expected outputs before any code.

Example: 01101111010

Index	Char	Event
0	0	Open a potential pattern
1	1	Scan through 1s
2	1	Continue scan
3	0	Pattern 1 found (0110). Pointer resets to index 3.
4	1	Open another potential pattern from index 3
5–7	1,1,1	Continue scan
8	0	Pattern 2 found (011110). Pointer resets to index 8.
9	1	Continue scan from index 8
10	0	Pattern 3 found (010).

Output: 3

Example: 01010

• Pattern 1 is 010 (indices 0 to 2). The 0 at index 2 immediately becomes the opening of the next potential pattern.
• Pattern 2 is 010 (indices 2 to 4).

Output: 2

Example: 0000

No 1 exists between any pair of 0s. Output: 0

How the Linear Scan Algorithm Works

The algorithm uses two integer pointers and a single forward pass. No extra data structure is needed.

Outer pointer i

Walk i from left to right through the string. Each time s[i] is '0', trigger the inner scan.

Inner pointer j

Start j at i + 1. Advance j forward as long as s[j] is '1'. Stop when j hits a non-1 character or the end of the string.

Match condition

Three conditions must all hold before recording a match:

• s[i] == '0' (opening zero confirmed)
• j > i + 1 (at least one 1 was scanned; this is the condition most textbook implementations omit)
• j < n and s[j] == '0' (closing zero present)

Skipping the j > i + 1 guard causes 00 to count as a valid pattern. For input "0000", that incorrect version returns 3 instead of 0.

Pointer reset after a match

When a match is confirmed, set i = j. The closing 0 at index j becomes the opening 0 for the next potential match. This is the rule that makes 01010 return 2 rather than 1. A version that advances i past the closing 0 after a match will under-count every input with back-to-back overlapping patterns.

C Program

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

int count_010_patterns(const char *s) {
    int n = (int)strlen(s);
    int count = 0;
    int i = 0;

    while (i < n) {
        if (s[i] == '0') {
            int j = i + 1;
            /* advance j through consecutive 1s */
            while (j < n && s[j] == '1') {
                j++;
            }
            /* match: at least one '1' found AND closing '0' present */
            if (j > i + 1 && j < n && s[j] == '0') {
                count++;
                i = j; /* closing '0' becomes the next opening '0' */
            } else {
                i++;
            }
        } else {
            i++;
        }
    }
    return count;
}

int main(void) {
    char s[1001];
    printf("Enter binary string: ");
    scanf("%1000s", s);
    printf("Total 0(1+)0 patterns: %d\n", count_010_patterns(s));
    return 0;
}

How to compile and run

gcc -o pattern pattern.c
./pattern
Enter binary string: 01101111010
Total 0(1+)0 patterns: 3

The j > i + 1 check is the guard that prevents 00 from counting. The i = j reset (not i = j followed by an immediate i++) is what enables overlapping counts.

Python Implementation

Two approaches work for Python. The choice depends on what the problem asks you to return.

Manual linear scan

The same two-pointer logic translates directly to Python:

def count_patterns_linear(s: str) -> int:
    n = len(s)
    count = 0
    i = 0
    while i < n:
        if s[i] == '0':
            j = i + 1
            while j < n and s[j] == '1':
                j += 1
            if j > i + 1 and j < n and s[j] == '0':
                count += 1
                i = j  # closing '0' starts the next scan
            else:
                i += 1
        else:
            i += 1
    return count

Regex with lookahead

The Python re module supports zero-width lookahead assertions. The pattern (?=(01+0)) finds every starting position in the string where 01+0 begins, without consuming characters. Because the lookahead is non-consuming, overlapping matches are found automatically.

import re

def count_patterns_regex(s: str) -> int:
    return len(re.findall(r'(?=(01+0))', s))

Both functions return 2 for 01010 and 3 for 01101111010. The regex version is two lines of production code; the manual version is more useful when the problem asks for the matched substrings or their start indices rather than just a count.

Quick verification

test_cases = [
    ("01101111010", 3),
    ("01010",       2),
    ("0000",        0),
    ("011110",      1),
    ("",            0),
]
for s, expected in test_cases:
    result = count_patterns_regex(s)
    status = "PASS" if result == expected else "FAIL"
    print(f"{status}  '{s}'  got {result}  expected {expected}")

All five cases pass with the corrected algorithm. The legacy version of this code (which skips the j > i + 1 guard and advances past the closing 0) fails on "01010" and "0000".

Edge Cases That Trip Up Interviews

The four inputs below collectively catch every common variant of this bug. Interviewers at Tier-1 tech companies often follow up with "01010" after an initial "01101111010" solution, specifically to probe whether the closing-zero-as-opening-zero rule is understood.

Empty string

With an empty string, the outer loop condition is false from the start. Both implementations return 0. No special handling needed.

All-zeros string

For input "0000", the inner scan for 1s finds none immediately at each position. The value of j equals i + 1 after the inner while-loop, so the j > i + 1 condition fails every time. The counter stays at 0. An implementation that omits this guard returns 3 for this input instead of 0.

All-ones string

For input "1111", the outer if s[i] == '0' branch never fires. The counter stays at 0. Both implementations handle this correctly with no modification.

Consecutive overlapping patterns

For input "01010", the correct output is 2. The 0 at index 2 ends the first pattern and simultaneously starts the second. Setting i = j (rather than i = j + 1) after a match is the single line that makes this work. The same boundary-accumulation reasoning appears in two-player coin game problems where one player’s last move sets the starting state for the next.

The pointer-reset discipline is a recurring pattern across string and array problems. It appears in palindrome pyramid generation, where character indices wrap from one row to the next, and in diamond and star pattern programs where boundary indices are reused across loops.

Time and Space Complexity

The algorithm runs in O(n) time. Each character is touched at most twice: once when the outer pointer i lands on it, and once more during the inner 1-scan if i landed on a '0' and the next character is a '1'. After a match, i jumps forward to j, so no character is rescanned after being part of a completed pattern. Space complexity is O(1): two integer pointers and a counter, no auxiliary array or stack.

Approach	Time	Space	Notes
Linear scan (this article)	O(n)	O(1)	Single pass, constant space
Regex lookahead re.findall	O(n)	O(k)	k equals the number of matches returned
Nested loop without pointer reset	O(n) worst case	O(1)	Degrades on long runs of 1s

The nested-loop version without the pointer reset is the most common wrong answer in placement submissions. It produces correct output for short test inputs but slows significantly on strings with extended runs of 1s.

For a different kind of range-scanning problem, finding valid house number ranges uses the same “advance to boundary then reset” approach, making it solid practice for the pointer discipline shown here.

From Placement Prep to Building Tools with LLMs

The regex lookahead (?=(01+0)) used in the Python section above is the same construct that appears when parsing semi-structured output from large language models. LLM responses rarely arrive as clean JSON; matching patterns that overlap token boundaries in raw text is a real production task. TinkerLLM is a structured environment for exactly that kind of experiment. At ₹299, it is a low-cost way to move from counting patterns in binary strings to writing prompts that extract patterns from natural language outputs.