Check if Binary String Has at Most One Segment of Ones — Easy Problem & Solution

A segment of ones is a maximal run of consecutive '1' characters.

Difficulty: Easy
Topics: Strings
Asked at: TCS, Infosys, Accenture
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A segment of ones is a maximal run of consecutive '1' characters.

Given a binary string s whose first character is '1', return true if it contains at most one such segment.

Example 1

Input: s = "1001"
Output: false
Explanation: Two segments: the leading 1 and the trailing 1.

Example 2

Input: s = "110"
Output: true
Explanation: One segment.

Example 3

Input: s = "1"
Output: true

Constraints

1 <= s.length <= 100
s[i] is '0' or '1'
s[0] is '1'.

How to solve Check if Binary String Has at Most One Segment of Ones

Segments are counted by their starting positions: a '1' whose predecessor is a '0' (or which is the first character) opens a new run. At most one such start means at most one segment.

Approach

Sweep the string counting positions where s[i] == '1' and either i == 0 or s[i-1] == '0'.
Return whether that count is at most 1.

Why it works

Every maximal run of ones has exactly one starting position under that test, and every position passing the test opens a run — so the count is exactly the number of segments.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Counting '1' characters rather than run starts answers a different question entirely.
The guarantee that s[0] == '1' is what makes the shortcut 'does the string contain 01' valid — without it, "0110" would fool it.

Reference solution

Python

def checkOnesSegment(s: str) -> bool:
    segments = 0
    for i, c in enumerate(s):
        if c == "1" and (i == 0 or s[i - 1] == "0"):
            segments += 1
    return segments <= 1

JavaScript

var checkOnesSegment = function(s) {
    var segments = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) === "1" && (i === 0 || s.charAt(i - 1) === "0")) segments++;
    }
    return segments <= 1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue