Check if Binary String Has at Most One Segment of Ones Solution
Check if Binary String Has at Most One Segment of Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if Binary String Has at Most One Segment of Ones is an easy coding problem on strings, asked in TCS, Infosys and Accenture interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: TCS, Infosys, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A segment of ones is a maximal run of consecutive '1' characters.
Given a binary string s whose first character is '1', return true if it contains at most one such segment.
Example 1
Input: s = "1001"
Output: false
Explanation: Two segments: the leading 1 and the trailing 1.
Example 2
Input: s = "110"
Output: true
Explanation: One segment.
Example 3
Input: s = "1"
Output: true
Constraints
1 <= s.length <= 100s[i] is '0' or '1's[0] is '1'.
Hints for Check if Binary String Has at Most One Segment of Ones
Hint 1
A new segment starts exactly where a
'1'follows a'0'(or begins the string).Hint 2
Count those starts and compare with 1.
Hint 3
Because the string starts with
'1', an equivalent check is simply: does"01"appear anywhere?
How to solve Check if Binary String Has at Most One Segment of Ones
Segments are counted by their starting positions: a '1' whose predecessor is a '0' (or which is the first character) opens a new run. At most one such start means at most one segment.
Approach
- Sweep the string counting positions where
s[i] == '1'and eitheri == 0ors[i-1] == '0'. - Return whether that count is at most 1.
Why it works
Every maximal run of ones has exactly one starting position under that test, and every position passing the test opens a run — so the count is exactly the number of segments.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Counting
'1'characters rather than run starts answers a different question entirely. - The guarantee that
s[0] == '1'is what makes the shortcut 'does the string contain 01' valid — without it,"0110"would fool it.
Reference solution
Python
def checkOnesSegment(s: str) -> bool:
segments = 0
for i, c in enumerate(s):
if c == "1" and (i == 0 or s[i - 1] == "0"):
segments += 1
return segments <= 1Java
public static boolean checkOnesSegment(String s) {
int segments = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1' && (i == 0 || s.charAt(i - 1) == '0')) segments++;
}
return segments <= 1;
}C++
bool checkOnesSegment(string s) {
int segments = 0;
for (int i = 0; i < (int) s.size(); i++) {
if (s[i] == '1' && (i == 0 || s[i - 1] == '0')) segments++;
}
return segments <= 1;
}JavaScript
var checkOnesSegment = function(s) {
var segments = 0;
for (var i = 0; i < s.length; i++) {
if (s.charAt(i) === "1" && (i === 0 || s.charAt(i - 1) === "0")) segments++;
}
return segments <= 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings