Check if Binary String Has at Most One Segment of Ones - Video Solutions

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.