Check if Binary String Has at Most One Segment of Ones

Check if Binary String Has at Most One Segment of Ones - Problem

String Easy

Given a binary string s without leading zeros, return true if s contains at most one contiguous segment of ones. Otherwise, return false.

A contiguous segment of ones is a substring that contains only the character '1' and is surrounded by '0' characters or string boundaries.

Input & Output

Example 1 — Single Segment

$ Input: s = "1001"

› Output: false

💡 Note: There are two segments of ones: "1" at position 0, and "1" at position 3. Since there are more than one segment, return false.

Example 2 — Contiguous Segment

$ Input: s = "110"

› Output: true

💡 Note: There is only one contiguous segment of ones: "11" at positions 0-1. Return true.

Example 3 — All Ones

$ Input: s = "1"

› Output: true

💡 Note: The string contains only one character '1', which forms exactly one segment. Return true.

Constraints

1 ≤ s.length ≤ 100
s[i] is either '0' or '1'
s[0] == '1' (no leading zeros)

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string without leading zeros

Process

Look for '01' pattern indicating multiple segments

Output

True if ≤1 segment, false if >1 segment

Key Takeaway

🎯 Key Insight: The pattern '01' can only exist if there are multiple segments of 1s separated by 0s

Asked in

a Amazon 15 M Microsoft 8

The key insight is that if a binary string has multiple segments of 1s, there must be a '0' followed by a '1' somewhere (the pattern '01'). Since the string has no leading zeros, finding this pattern guarantees multiple segments. Best approach scans for '01' pattern in O(n) time, O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Pattern Detection	O(n)	O(1)	Look for '01' pattern which indicates multiple segments
Brute Force - Count All Segments	O(n)	O(1)	Find all contiguous segments of 1s and count them

Optimized - Pattern Detection — Algorithm Steps

Iterate through the string looking for consecutive characters
If we find '01' pattern, return false immediately
If we complete the scan without finding '01', return true

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Look for consecutive '01' pattern

Detect

If '01' found, multiple segments exist

Result

Return false if pattern found, true otherwise

Code -

solution.c — C

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

bool solution(char* s) {
    // Look for pattern '01' which indicates multiple segments
    int len = strlen(s);
    for (int i = 0; i < len - 1; i++) {
        if (s[i] == '0' && s[i + 1] == '1') {
            return false;
        }
    }
    return true;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, may terminate early

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space

✓ Linear Space

23.4K Views

Medium Frequency

~10 min Avg. Time

892 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

Optimized - Pattern Detection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler