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 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 \(\textit{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 \(\textit{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)\).

1
2
3

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

1
2
3
4
5

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

1
2
3
4
5
6

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

1
2
3

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

1
2
3

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

1
2
3
4
5

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

1
2
3
4
5
6
7

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

Comments