Given a binary string s without leading zeros, return true if s contains at most one contiguous segment of ones. Otherwise, return false.
Example 1:
Input: s = "1001" Output: false Explanation: The ones do not form a contiguous segment.
Example 2:
Input: s = "110" Output: true
Constraints:
1 <= s.length <= 100s[i] is either '0' or '1'.s[0] is '1'.Problem Overview: You are given a binary string containing only 0 and 1. The task is to verify that all 1s appear in a single contiguous block. Once a 0 appears after the first 1, another 1 later in the string would create a second segment and the answer becomes false.
Approach 1: Single Pass Using Flag (O(n) time, O(1) space)
Scan the string once from left to right. Track whether a zero has appeared after the first sequence of ones. When you encounter a 1, mark that the segment of ones has started. If you later see a 0, record that the segment has ended. Any subsequent 1 after this point means a second segment exists, so return false. This solution relies on simple state tracking while iterating through the string, making it a clean string traversal problem. Time complexity is O(n) because each character is visited once, and space complexity is O(1) since only a couple of boolean flags are used.
Approach 2: Count Split Points (O(n) time, O(n) space)
Another way to reason about the problem is to count how many groups of 1s exist. Split the string around 0 characters and inspect the resulting substrings. Every non-empty substring represents a contiguous segment of ones. If more than one non-empty segment exists, the string contains multiple blocks of ones and should return false. This approach is conceptually simple because it directly measures the number of segments. However, the split operation allocates extra memory for substrings, so the space complexity becomes O(n). The time complexity remains O(n) because the string is processed once during the split and counting steps.
Recommended for interviews: The single-pass flag solution is the one interviewers typically expect. It demonstrates that you can reason about state changes while iterating through a string and avoid unnecessary allocations. The split-based method is easier to think about initially and shows correct problem understanding, but the optimal implementation uses constant space and a single scan. Problems like this frequently appear in basic string manipulation and lightweight greedy reasoning tasks where maintaining minimal state during traversal leads to the cleanest solution.
This approach involves iterating through the string once and using a flag to check for transitions between '1' and '0'. When we encounter a '0' after finding a '1', we set a flag. If we find another '1' afterwards, it indicates more than one segment of '1's.
The function iterates over the string using a loop. A boolean variable found_zero is used to check if '0' has been found after a '1'. If a '1' is found after found_zero is set to true, return false. Otherwise, return true after the loop ends.
Time Complexity: O(n) where n is the length of the string since we only traverse the string once.
Space Complexity: O(1) as we use a constant amount of extra space.
This method involves counting the number of times the string changes from '1' to '0' and back to '1'. If this transition happens more than once, the function returns false, otherwise true.
Start the loop from the second character and check if a '1' follows a '0'. Increment the splits counter when this pattern is found. Return true if splits remains 0.
Time Complexity: O(n)
Space Complexity: O(1)
Since the string s has no leading zeros, s starts with '1'.
If the string s contains the substring "01", then s is of the form "1...01...", which means s has at least two separate segments of consecutive '1's, violating the condition — return false.
If the string s does not contain the substring "01", then s can only be of the form "1..1000...", which means s has exactly one segment of consecutive '1's, satisfying the condition — return true.
Therefore, we only need to check whether the string s contains the substring "01".
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Single Pass Using Flag | Time Complexity: O(n) where n is the length of the string since we only traverse the string once. |
| Approach 2: Count Split Points | Time Complexity: O(n) |
| Brain Teaser | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass Using Flag | O(n) | O(1) | Best general solution. Efficient single traversal with constant memory. |
| Count Split Points | O(n) | O(n) | Useful for quick reasoning or scripting languages where string splitting is convenient. |
Check if Binary String Has at Most One Segment of Ones | Two Approaches | Leetcode 1784 | MIK • codestorywithMIK • 4,090 views views
Watch 9 more video solutions →Practice Check if Binary String Has at Most One Segment of Ones with our built-in code editor and test cases.
Practice on FleetCode