Check if Binary String Has at Most One Segment of Ones
EasyPrompt
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'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach first identifies the end of the initial contiguous segment of ones. Then, it performs a second scan on the rest of the string to ensure no more ones are present.
Algorithm
- Find the index of the first '0' in the string. Let this be
firstZeroIndex. - If no '0' is found, the entire string is composed of '1's, which forms a single segment. Return
true. - If a '0' is found, iterate from
firstZeroIndex + 1to the end of the string. - In this second scan, if a '1' is found, it means there is another segment of ones. Return
false. - If the second scan completes without finding any '1's, it means there is only one segment. Return
true.
Walkthrough
The algorithm starts by finding the first occurrence of a '0'. Since the string is guaranteed to start with '1', the initial part of the string will be a segment of ones. We iterate from the beginning of the string to find the index of the first '0'. If no '0' is found, it means the entire string consists of ones, which is a single segment, so we return true. If a '0' is found at firstZeroIndex, we then iterate through the rest of the string, from firstZeroIndex + 1 to the end. During this second iteration, if we encounter any '1', it signifies the beginning of a new segment of ones, and we can immediately return false. If the second loop completes without finding any '1's, we return true.
class Solution { public boolean checkOnesSegment(String s) { int firstZeroIndex = -1; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '0') { firstZeroIndex = i; break; } } // If no '0' was found, the string is all '1's, which is one segment. if (firstZeroIndex == -1) { return true; } // Check the rest of the string for any '1's. for (int i = firstZeroIndex + 1; i < s.length(); i++) { if (s.charAt(i) == '1') { return false; // Found a second segment of ones. } } return true; }}Complexity
Time
O(N), where N is the length of the string. Although there are two loops, each character is visited at most a constant number of times, resulting in linear time complexity.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
The logic is straightforward and easy to follow, breaking the problem into two distinct steps.
Cons
Slightly less efficient than a single-pass solution as it might iterate over parts of the string twice.
The code is more verbose compared to more optimized approaches.
This approach improves upon the two-pass method by using a single loop and a boolean flag to keep track of whether a '0' has been encountered.
Algorithm
- Initialize a boolean flag,
foundZero, tofalse. - Iterate through the string
sfrom the second character (index 1) to the end. - If the current character is '0', set
foundZerototrue. - If the current character is '1' and
foundZerois alreadytrue, it means we have found a '1' that appears after a '0'. This indicates a second segment, so returnfalse. - If the loop completes without returning
false, it means there is at most one segment of ones. Returntrue.
Walkthrough
The core idea is that a second segment of ones can only exist if a '1' appears after a '0'. We can iterate through the string once, keeping track of the state with a boolean flag, foundZero, initialized to false. As we iterate, if we encounter a '0', we set the foundZero flag to true. If we later encounter a '1' after the foundZero flag has been set, it confirms the existence of a second segment of ones, so we can immediately return false. If the loop finishes, it means the string has at most one segment of ones, so we return true.
class Solution { public boolean checkOnesSegment(String s) { boolean foundZero = false; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == '0') { foundZero = true; } else if (foundZero) { // s.charAt(i) == '1' and we've already seen a '0' return false; } } return true; }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string exactly once.
Space
O(1), as we only use a single boolean flag for storage.
Trade-offs
Pros
Efficient, requiring only a single pass through the string.
Simple to implement and understand.
Cons
While efficient, the logic can be expressed even more concisely using built-in string methods.
This is the most concise and elegant approach. It leverages the key insight that multiple segments of ones can only exist if there is a transition from '0' back to '1'.
Algorithm
- The problem can be simplified to checking for the existence of the substring "01".
- If a string has more than one segment of ones, it must contain a '0' followed by a '1'. For example,
1101. - If a string has at most one segment of ones, it will have the form
1...10...0and will never contain the substring "01". - Use a built-in string method to check if
scontains "01". - Return
trueif it does not contain "01", andfalseif it does.
Walkthrough
A binary string has more than one segment of ones if and only if a '1' appears somewhere after a '0'. This creates the pattern "01". Conversely, if the string contains at most one segment of ones, it will look like a sequence of ones followed by a sequence of zeros (e.g., "11100" or "111"). Such a string will never contain the substring "01". Therefore, the problem is equivalent to checking if the string s contains the substring "01". We can use a built-in contains() method to perform this check efficiently. If s.contains("01") is true, we return false; otherwise, we return true.
class Solution { public boolean checkOnesSegment(String s) { // If the string contains "01", it means a segment of ones is broken by a zero, // and then another one appears. This implies more than one segment. return !s.contains("01"); }}Complexity
Time
O(N), where N is the length of the string. The `contains` method performs a linear scan of the string to find the substring.
Space
O(1). The space required for the substring "01" is constant, and the `contains` method typically operates in constant extra space.
Trade-offs
Pros
Extremely concise, readable, and idiomatic.
Leverages highly optimized built-in library functions.
Asymptotically as efficient as a manual single-pass iteration.
Cons
Abstracts away the underlying iteration, which might be less instructive for beginners learning about basic loop-based algorithms.
Solutions
Solution
class Solution {public boolean checkOnesSegment(String s) { return !s.contains("01"); }}class Solution {public: bool checkOnesSegment(string s) { return s.find("01") == -1; }};class Solution: def checkOnesSegment(self, s: str) -> bool: return '01' not in sVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.