Problem

Given a binary string s ​​​​​without leading zeros , return true​​​ ifs containsat most one contiguous segment of ones. Otherwise, return false.

Examples

Example 1

1
2
3

Input: s = "1001"
Output: false
Explanation: The ones do not form a contiguous segment.

Example 2

1
2

Input: s = "110"
Output: true

Constraints

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

Solution

Method 1 – Scan for ‘01’ Pattern

Intuition

A binary string has at most one segment of ones if there is no ‘01’ followed by another ‘1’. In other words, once a ‘0’ appears after a ‘1’, there should be no more ‘1’s. We can check for the pattern ‘01’ and ensure it only occurs once at most.

Approach

  1. Scan the string from left to right.
  2. Once a ‘0’ is found after a ‘1’, check if any ‘1’ appears after that.
  3. If so, return false; otherwise, return true.
  4. Alternatively, check if the string contains the substring ‘01’ more than once or if ‘10’ is followed by ‘1’.
  5. The simplest way: check if ‘01’ appears more than once or if ‘10’ is followed by ‘1’.

Code

1
2
3
4
5
6

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

func checkOnesSegment(s string) bool {
    return !strings.Contains(s, "01")
}
1
2
3
4
5

class Solution {
    public boolean checkOnesSegment(String s) {
        return !s.contains("01");
    }
}
1
2
3
4
5

class Solution {
    fun checkOnesSegment(s: String): Boolean {
        return !s.contains("01")
    }
}
1
2
3

class Solution:
    def checkOnesSegment(self, s: str) -> bool:
        return '01' not in s
1
2
3
4
5

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

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(1)