Scale Engineer

Check if Binary String Has at Most One Segment of Ones

Easy
#1632Time: 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.1 company
Data structures
String
Companies
Cisco

Prompt

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 <= 100
  • s[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 + 1 to 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.

Solutions

class Solution {public  boolean checkOnesSegment(String s) { return !s.contains("01"); }}

Video 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.

← Previous

Previous problem

Next →

Next problem