Skip to main content
Talentd

Check if Binary String Has at Most One Segment of Ones - Solution & Explanation

EasyString13 min readAsked at: Amazon, Cisco, Google
Practice this problem

Problem Statement

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

Approach Overview

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.

Approach 1: Approach 1: Single Pass Using Flag

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Count Split Points

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Brain Teaser

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

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) as we use a constant amount of extra space.

Approach 2: Count Split Points

Time Complexity: O(n)
Space Complexity: O(1)

Brain Teaser—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Single Pass Using FlagO(n)O(1)Best general solution. Efficient single traversal with constant memory.
Count Split PointsO(n)O(n)Useful for quick reasoning or scripting languages where string splitting is convenient.

Video Solution

Check if Binary String Has at Most One Segment of Ones | Two Approaches | Leetcode 1784 | MIK • codestorywithMIK • 4,208 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Check if Binary String Has at Most One Segment of Ones easy or hard?
The problem is classified as Easy. It focuses on careful string traversal and state tracking rather than complex algorithms or data structures.
Check if Binary String Has at Most One Segment of Ones Python/Java solution
In Python or Java, iterate through the characters and track whether a zero has appeared after the first 1. If another 1 appears afterward, return false. The implementation takes O(n) time and O(1) extra space.
How to solve Check if Binary String Has at Most One Segment of Ones in O(n)?
Iterate through the string while tracking whether a zero has appeared after the first block of ones. If you encounter a 1 after such a zero, immediately return false. Completing the scan without this condition means there is at most one segment of ones.
What is the best approach for Check if Binary String Has at Most One Segment of Ones?
The most efficient approach is a single-pass traversal using a flag to track whether the sequence of ones has ended. Once a zero appears after the first 1, any later 1 indicates a second segment. This method runs in O(n) time with O(1) extra space.
Is Check if Binary String Has at Most One Segment of Ones asked at Google/Amazon/Meta?
This exact problem is commonly used for practice on coding platforms and reflects the type of basic string reasoning questions asked in screening rounds. Similar problems appear in interviews at companies like Amazon and Google when testing simple traversal and state tracking skills.
What data structure is used in Check if Binary String Has at Most One Segment of Ones?
No complex data structures are required. The optimal approach only uses simple variables while iterating through the string. Some alternative solutions temporarily create arrays of substrings after splitting the string by zeros.
What is the time complexity of Check if Binary String Has at Most One Segment of Ones?
The optimal solution runs in O(n) time because the string is scanned once from left to right. Only constant extra variables are used to track state, so the space complexity is O(1).

Ready to solve this problem?

Practice Check if Binary String Has at Most One Segment of Ones with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longer Contiguous Segments of Ones than Zeros