LeetCode 1784 — Check if Binary String Has at Most One Segment of Ones
LeetCode 1784 – Check if Binary String Has at Most One Segment of Ones
In this article, we will understand how to solve LeetCode Problem 1784 using a clear step-by-step approach. We will break down the intuition, the problem, and implement an efficient Java solution.
Problem Statement
You are given a binary string s consisting only of characters 0 and 1.
Your task is to determine whether the string contains at most one continuous segment of ones.
- Return true if there is only one segment of ones.
- Return false if there are multiple segments of ones.
Understanding What a Segment Means
A segment of ones means a continuous group of the character 1.
Examples:
111 → One segment 0011100 → One segment 101 → Two segments 110011 → Two segments
Example Walkthrough
Example 1
Input: s = "110"
Index: 0 1 2
1 1 0
There is only one continuous group of ones:
[11]
Output: true
Example 2
Input: s = "1001"
Index: 0 1 2 3
1 0 0 1
Here we have two separate segments:
[1] [1]
Since there are multiple segments of ones, the answer becomes:
Output: false
Key Observation And Important Interview Insight
If a binary string has more than one segment of ones, it must contain the pattern:
01 ... 1
That means ones ended and later started again.
The easiest way to detect this situation is to look for the pattern:
"01"
If we ever see 0 followed by 1, it means a new segment of ones started.
Pointer Movement
Consider the string:
s = "110011"
Step-by-step scanning:
Index: 0 1 2 3 4 5
1 1 0 0 1 1
↑
Start of first segment
Index: 0 1 2 3 4 5
1 1 0 0 1 1
↑
Still in the same segment
Index: 0 1 2 3 4 5
1 1 0 0 1 1
↑
Segment ended
Index: 0 1 2 3 4 5
1 1 0 0 1 1
↑
New segment detected → INVALID
Optimal Java Solution
We simply scan the string and check whether a 0 is followed by 1.
class Solution {
public boolean checkOnesSegment(String s) {
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == '0' && s.charAt(i + 1) == '1') {
return false;
}
}
return true;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
Shorter Java Solution (Elegant Trick)
We can also directly check if the string contains the pattern "01".
class Solution {
public boolean checkOnesSegment(String s) {
return !s.contains("01");
}
}
This works because once ones stop and later appear again, the string must contain 01.
Alternative Approaches
1. Counting Segments
Count how many times a new segment of ones starts.
class Solution {
public boolean checkOnesSegment(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1' && (i == 0 || s.charAt(i - 1) == '0')) {
count++;
}
if (count > 1) {
return false;
}
}
return true;
}
}
Edge Cases
"1" → true "111" → true "000" → true "10" → true "101" → false "110011" → false
Conclusion
The key idea in this problem is recognizing that a second segment of ones must contain the pattern "01".
Therefore, the simplest and most elegant solution is checking:
!s.contains("01")
This approach runs in linear time and is perfect for coding interviews.