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

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

In this problem, we are given a binary string s that contains only the characters '0' and '1'. The string is guaranteed to begin with '1', which means there are no leading zeros. The task is to determine whether the string contains at most one contiguous segment of ones.

A contiguous segment of ones means a sequence of consecutive '1' characters without interruption. For example:

"111" contains one segment of ones.
"110011" contains two segments of ones.
"1000" contains one segment of ones.
"10101" contains three separate segments of ones.

The expected output is a boolean value:

Return true if the string has zero or one segment of ones.
Return false if the string has two or more separate segments of ones.

The constraints are very small:

The string length is between 1 and 100.
Every character is either '0' or '1'.
The first character is always '1'.

These constraints tell us that even inefficient solutions would run quickly. However, the goal is still to design a clean and correct algorithm.

An important observation is that because the string always starts with '1', the first segment of ones always begins at index 0. Therefore, the only thing we need to detect is whether another '1' appears after a '0' has already ended the first segment.

Several edge cases are important:

A string containing only ones, such as "11111", should return true.
A string with one segment followed by zeros, such as "111000", should return true.
A string where ones reappear after zeros, such as "110011", should return false.
A single-character string "1" should return true.

Approaches

Brute Force Approach

A straightforward approach is to explicitly count the number of contiguous segments of ones.

We can scan the string from left to right and detect the start of each new segment of ones. A new segment begins whenever:

The current character is '1', and
Either it is the first character, or the previous character is '0'.

Every time this condition occurs, we increment a counter. At the end, we return whether the counter is less than or equal to one.

This approach is correct because every contiguous group of ones has exactly one starting position. By counting those starting positions, we count the number of segments.

Although this solution is already efficient enough for the given constraints, we can simplify the logic even further.

Optimal Approach

The key observation is that the string starts with '1'. Therefore, the first segment of ones must begin at the start of the string.

If we ever encounter the substring "01", it means:

A segment of ones ended at the '0'
Another segment of ones started at the following '1'

That immediately proves there are at least two segments of ones.

So the problem reduces to checking whether the string contains "01".

If "01" exists, return false.
Otherwise, return true.

This leads to a very concise and efficient solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Counts contiguous segments of ones
Optimal	O(n)	O(1)	Detects whether `"01"` exists

Algorithm Walkthrough

Start scanning the string from left to right.
Check whether the substring "01" appears anywhere in the string. This pattern is important because it represents the end of one segment of ones and the beginning of another.
If "01" is found, immediately return false, because the string contains more than one segment of ones.
If the scan finishes without finding "01", return true, because all ones belong to a single contiguous segment.

Why it works

The string begins with '1', so the first segment of ones always starts at index 0. A second segment can only appear if ones occur again after a zero. The substring "01" captures exactly that transition. Therefore, the existence of "01" is equivalent to having more than one segment of ones.

Python Solution

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        return "01" not in s

The implementation relies entirely on the core observation of the problem.

The expression "01" in s checks whether the string contains a zero followed immediately by a one. If such a pattern exists, then the string must contain at least two separate segments of ones.

By returning "01" not in s, we return True only when the string contains at most one segment of ones.

The solution is concise because Python provides efficient substring search operations directly on strings.

Go Solution

func checkOnesSegment(s string) bool {
    for i := 0; i < len(s)-1; i++ {
        if s[i] == '0' && s[i+1] == '1' {
            return false
        }
    }

    return true
}

The Go implementation performs the substring detection manually by scanning adjacent characters.

At each index, it checks whether the current character is '0' and the next character is '1'. If that pattern is found, the function immediately returns false.

Unlike Python, Go does not have as concise a built-in substring syntax for this exact use case, so a loop is the clearest approach.

There are no concerns about integer overflow or special memory handling because the input size is very small and the algorithm uses constant extra space.

Worked Examples

Example 1

Input:

s = "1001"

We scan for the pattern "01".

Index	Current Pair	Contains "01"?	Result
0	"10"	No	Continue
1	"00"	No	Continue
2	"01"	Yes	Return false

The algorithm returns false because a second segment of ones appears at the end.

Example 2

Input:

s = "110"

Index	Current Pair	Contains "01"?	Result
0	"11"	No	Continue
1	"10"	No	Continue

The scan finishes without finding "01".

The algorithm returns true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The string is scanned once
Space	O(1)	Only constant extra memory is used

The algorithm examines each character at most once, so the running time grows linearly with the length of the string. No auxiliary data structures are needed, which keeps the space usage constant.

Test Cases

solution = Solution()

assert solution.checkOnesSegment("1") == True          # Single character
assert solution.checkOnesSegment("11111") == True     # All ones
assert solution.checkOnesSegment("110") == True       # One segment followed by zero
assert solution.checkOnesSegment("1000") == True      # One single one
assert solution.checkOnesSegment("111000") == True    # One long segment then zeros

assert solution.checkOnesSegment("101") == False      # Two separate one segments
assert solution.checkOnesSegment("1001") == False     # Ones reappear after zeros
assert solution.checkOnesSegment("110011") == False   # Multiple separated segments
assert solution.checkOnesSegment("10101") == False    # Alternating ones and zeros
assert solution.checkOnesSegment("1100011") == False  # Large gap between segments

Test	Why
`"1"`	Smallest valid input
`"11111"`	Entire string is one segment
`"110"`	One segment followed by zeros
`"1000"`	Single one at beginning
`"111000"`	Continuous ones then continuous zeros
`"101"`	Detects two separate segments
`"1001"`	Detects separated ones after zeros
`"110011"`	Multiple distinct segments
`"10101"`	Alternating pattern stresses detection
`"1100011"`	Ensures later segments are detected

Edge Cases

One important edge case is a string containing only one character, such as "1". A careless implementation might incorrectly assume there are at least two characters when checking adjacent pairs. The provided solutions handle this correctly because the loop simply does not execute when the string length is one.

Another important case is a string consisting entirely of ones, such as "111111". In this situation, there is exactly one contiguous segment. The algorithm correctly returns true because the substring "01" never appears.

A third important edge case is when ones reappear after a long sequence of zeros, such as "1000001". Some naive solutions might incorrectly stop checking after the first zero. The implemented algorithm continues scanning the entire string, so it correctly detects the "01" pattern near the end and returns false.

A final subtle case is "10". There is one segment of ones followed by zeros, which is valid. The algorithm correctly returns true because there is no occurrence of "01".