Check if Binary String Has at Most One Segment of Ones solution and explanation
Cisco
Google
9 more videos on this problem
Check if Binary String Has at Most One Segment of Ones | Two Approaches | Leetcode 1784 | MIKcodestorywithMIK · 7:28 · 4K views
1784. Check if Binary String Has at Most One Segment of Ones (Leetcode Easy)Programming Live with Larry · 2:55 · 892 views
1784. Check if Binary String Has at Most One Segment of Ones | Leetcode Daily - PythonLeetcode Daily · 6:23 · 411 views
Daily Leetcode #2166: Mar 06, 2026 - 1784. Check if Binary String Has at Most One Segment of OnesProgramming Live with Larry · 5:31 · 251 views
LeetCode 1784 Check if Binary String Has at Most One Segment of Ones | Easy | StringCode Harmony · 10:47 · 175 views
Leetcode 1784. Check if Binary String Has at Most One Segment of Ones | Simple Logic ExplainedCode Crusaders · 2:38 · 173 views
Check if Binary String Has at Most One Segment of Ones | LeetCode 1784 | Java Code | Developer CoderDeveloper Coder · 8:39 · 127 views
Check if Binary String Has at Most One Segment of Ones | LeetCode 1784 - Pythonimpoldev · 3:39 · 120 views
Check if Binary String has at Most One Segment of Ones | Leetcode 1784 | Java Hindi | Daily LeetcodeKernel Queen 👑 · 1:40 · 114 views
1784. Check if Binary String Has at Most One Segment of Ones - JavaScript - One LineAlgoPrepMaster · 0:22 · 67 views
The problem
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'.
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.
def checkOnesSegment(s: str) -> bool:
found_zero = False
for char in s:
if char == '0':
found_zero = True
if found_zero and char == '1':
return False
return Trueclass Solution {
public boolean checkOnesSegment(String s) {
boolean foundZero = false;
for (char c : s.toCharArray()) {
if (c == '0') foundZero = true;
if (foundZero && c == '1') return false;
}
return true;
}
}#include <string>
class Solution {
public:
bool checkOnesSegment(std::string s) {
bool found_zero = false;
for (char c : s) {
if (c == '0') found_zero = true;
if (found_zero && c == '1') return false;
}
return true;
}
};function checkOnesSegment(s) {
let foundZero = false;
for (let i = 0; i < s.length; i++) {
if (s[i] === '0') {
foundZero = true;
}
if (foundZero && s[i] === '1') {
return false;
}
}
return true;
}#include <stdbool.h>
#include <string.h>
bool checkOnesSegment(char * s) {
bool found_zero = false;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '0') {
found_zero = true;
}
if (found_zero && s[i] == '1') {
return false;
}
}
return true;
}public class Solution {
public bool CheckOnesSegment(string s) {
bool foundZero = false;
foreach (char c in s) {
if (c == '0') foundZero = true;
if (foundZero && c == '1') return false;
}
return true;
}
}The Python implementation uses a for loop to iterate over the string. The boolean flag found_zero determines if there is a transition from '0' back to '1', returning False if such a transition is detected.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def checkOnesSegment(s: str) -> bool:
splits = 0
for i in range(1, len(s)):
if s[i] == '1' and s[i - 1] == '0':
splits += 1
return splits == 0class Solution {
public boolean checkOnesSegment(String s) {
int splits = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '1' && s.charAt(i - 1) == '0') {
splits++;
}
}
return splits == 0;
}
}#include <string>
class Solution {
public:
bool checkOnesSegment(std::string s) {
int splits = 0;
for (size_t i = 1; i < s.length(); ++i) {
if (s[i] == '1' && s[i - 1] == '0') {
++splits;
}
}
return splits == 0;
}
};function checkOnesSegment(s) {
let splits = 0;
for (let i = 1; i < s.length; i++) {
if (s[i] === '1' && s[i - 1] === '0') {
splits++;
}
}
return splits === 0;
}#include <stdbool.h>
#include <string.h>
bool checkOnesSegment(char * s) {
int splits = 0;
for (int i = 1; s[i] != '\0'; ++i) {
if (s[i] == '1' && s[i - 1] == '0') {
++splits;
}
}
return splits == 0;
}public class Solution {
public bool CheckOnesSegment(string s) {
int splits = 0;
for (int i = 1; i < s.Length; i++) {
if (s[i] == '1' && s[i - 1] == '0') {
splits++;
}
}
return splits == 0;
}
}The Python version also counts transitions from '0' to '1', starting from index 1. The lack of multiple transitions (i.e., splits == 0) means one segment.
Time Complexity: O(n)
Space Complexity: O(1)
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).
function checkOnesSegment(s: string): boolean {
return !s.includes('01');
}func checkOnesSegment(s string) bool {
return !strings.Contains(s, "01")
}impl Solution {
pub fn check_ones_segment(s: String) -> bool {
!s.contains("01")
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Single Pass Using Flag | Time Complexity: O(n) |
| Approach 2: Count Split Points | Time Complexity: O(n) |
| Brain Teaser | – |
Complexity analysis
| 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. |
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).