LeetCode 1784. Check if Binary String Has at Most One Segment of Ones Solution in Java, C++, Python & More | Explanation + Code

Description

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 string has two segments of size 1.

Example 2:

Input: s = "110"
Output: true

 

Constraints:

• 1 <= s.length <= 100
• s[i]​​​​ is either '0' or '1'.
• s[0] is '1'.

Solutions

Solution 1: 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).

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def checkOnesSegment(self, s: str) -> bool: return '01' not in s(code-box)

class Solution { public boolean checkOnesSegment(String s) { return !s.contains("01"); } }(code-box)

class Solution { public: bool checkOnesSegment(string s) { return s.find("01") == -1; } };(code-box)

func checkOnesSegment(s string) bool { return !strings.Contains(s, "01") }(code-box)

function checkOnesSegment(s: string): boolean { return !s.includes('01'); }(code-box)

impl Solution { pub fn check_ones_segment(s: String) -> bool { !s.contains("01") } }(code-box)

/** * @param {string} s * @return {boolean} */ var checkOnesSegment = function (s) { return !s.includes('01'); };(code-box)