1784. Check if Binary String Has at Most One Segment of Ones

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 ones do not form a contiguous segment.

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: No '1' After '0'

Notice that the string \(s\) does not contain leading zeros, which means \(s\) starts with '1'.

If the string \(s\) contains the substring "01", then \(s\) must be a string like "1...01...", in which case \(s\) has at least two consecutive '1' segments, which does not satisfy the problem condition, so we return false.

If the string \(s\) does not contain the substring "01", then \(s\) can only be a string like "1..1000...", in which case \(s\) has only one consecutive '1' segment, which satisfies the problem condition, so we return true.

Therefore, we only need to judge 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)\).

Python3JavaC++GoTypeScriptRust

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

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

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

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

function checkOnesSegment(s: string): boolean {
    let pre = s[0];
    for (const c of s) {
        if (pre !== c && c === '1') {
            return false;
        }
        pre = c;
    }
    return true;
}

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

Solution 2

TypeScript

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

Comments