# Check if Binary String Has at Most One Segment of Ones
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-binary-string-has-at-most-one-segment-of-ones)
Canonical: https://scaleengineer.com/dsa/problems/check-if-binary-string-has-at-most-one-segment-of-ones
**Data structures:** String
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## Problem
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'`.

# Approaches
## Two-Pass Iteration
This approach first identifies the end of the initial contiguous segment of ones. Then, it performs a second scan on the rest of the string to ensure no more ones are present.
**Time:** O(N), where N is the length of the string. Although there are two loops, each character is visited at most a constant number of times, resulting in linear time complexity. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** The logic is straightforward and easy to follow, breaking the problem into two distinct steps.
**Cons:** Slightly less efficient than a single-pass solution as it might iterate over parts of the string twice.; The code is more verbose compared to more optimized approaches.
### Explanation
The algorithm starts by finding the first occurrence of a '0'. Since the string is guaranteed to start with '1', the initial part of the string will be a segment of ones. We iterate from the beginning of the string to find the index of the first '0'. If no '0' is found, it means the entire string consists of ones, which is a single segment, so we return `true`. If a '0' is found at `firstZeroIndex`, we then iterate through the rest of the string, from `firstZeroIndex + 1` to the end. During this second iteration, if we encounter any '1', it signifies the beginning of a new segment of ones, and we can immediately return `false`. If the second loop completes without finding any '1's, we return `true`.

```java
class Solution {
    public boolean checkOnesSegment(String s) {
        int firstZeroIndex = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                firstZeroIndex = i;
                break;
            }
        }

        // If no '0' was found, the string is all '1's, which is one segment.
        if (firstZeroIndex == -1) {
            return true;
        }

        // Check the rest of the string for any '1's.
        for (int i = firstZeroIndex + 1; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                return false; // Found a second segment of ones.
            }
        }

        return true;
    }
}
```
### Algorithm
- Find the index of the first '0' in the string. Let this be `firstZeroIndex`.
- If no '0' is found, the entire string is composed of '1's, which forms a single segment. Return `true`.
- If a '0' is found, iterate from `firstZeroIndex + 1` to the end of the string.
- In this second scan, if a '1' is found, it means there is another segment of ones. Return `false`.
- If the second scan completes without finding any '1's, it means there is only one segment. Return `true`.

## Single-Pass Iteration with Flag
This approach improves upon the two-pass method by using a single loop and a boolean flag to keep track of whether a '0' has been encountered.
**Time:** O(N), where N is the length of the string. We iterate through the string exactly once. · **Space:** O(1), as we only use a single boolean flag for storage.
**Pros:** Efficient, requiring only a single pass through the string.; Simple to implement and understand.
**Cons:** While efficient, the logic can be expressed even more concisely using built-in string methods.
### Explanation
The core idea is that a second segment of ones can only exist if a '1' appears after a '0'. We can iterate through the string once, keeping track of the state with a boolean flag, `foundZero`, initialized to `false`. As we iterate, if we encounter a '0', we set the `foundZero` flag to `true`. If we later encounter a '1' *after* the `foundZero` flag has been set, it confirms the existence of a second segment of ones, so we can immediately return `false`. If the loop finishes, it means the string has at most one segment of ones, so we return `true`.

```java
class Solution {
    public boolean checkOnesSegment(String s) {
        boolean foundZero = false;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                foundZero = true;
            } else if (foundZero) { // s.charAt(i) == '1' and we've already seen a '0'
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize a boolean flag, `foundZero`, to `false`.
- Iterate through the string `s` from the second character (index 1) to the end.
- If the current character is '0', set `foundZero` to `true`.
- If the current character is '1' and `foundZero` is already `true`, it means we have found a '1' that appears after a '0'. This indicates a second segment, so return `false`.
- If the loop completes without returning `false`, it means there is at most one segment of ones. Return `true`.

## Built-in Substring Search
This is the most concise and elegant approach. It leverages the key insight that multiple segments of ones can only exist if there is a transition from '0' back to '1'.
**Time:** O(N), where N is the length of the string. The `contains` method performs a linear scan of the string to find the substring. · **Space:** O(1). The space required for the substring "01" is constant, and the `contains` method typically operates in constant extra space.
**Pros:** Extremely concise, readable, and idiomatic.; Leverages highly optimized built-in library functions.; Asymptotically as efficient as a manual single-pass iteration.
**Cons:** Abstracts away the underlying iteration, which might be less instructive for beginners learning about basic loop-based algorithms.
### Explanation
A binary string has more than one segment of ones if and only if a '1' appears somewhere after a '0'. This creates the pattern "01". Conversely, if the string contains at most one segment of ones, it will look like a sequence of ones followed by a sequence of zeros (e.g., "11100" or "111"). Such a string will never contain the substring "01". Therefore, the problem is equivalent to checking if the string `s` contains the substring "01". We can use a built-in `contains()` method to perform this check efficiently. If `s.contains("01")` is true, we return `false`; otherwise, we return `true`.

```java
class Solution {
    public boolean checkOnesSegment(String s) {
        // If the string contains "01", it means a segment of ones is broken by a zero,
        // and then another one appears. This implies more than one segment.
        return !s.contains("01");
    }
}
```
### Algorithm
- The problem can be simplified to checking for the existence of the substring "01".
- If a string has more than one segment of ones, it must contain a '0' followed by a '1'. For example, `1101`.
- If a string has at most one segment of ones, it will have the form `1...10...0` and will never contain the substring "01".
- Use a built-in string method to check if `s` contains "01".
- Return `true` if it does not contain "01", and `false` if it does.

# Solutions
### Java

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

```

### CPP

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

```

### Python

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

```