# Longer Contiguous Segments of Ones than Zeros
**Difficulty:** EASY
[External](https://leetcode.com/problems/longer-contiguous-segments-of-ones-than-zeros)
Canonical: https://scaleengineer.com/dsa/problems/longer-contiguous-segments-of-ones-than-zeros
**Data structures:** String
---
## Problem
Given a binary string `s`, return `true` _if the **longest** contiguous segment of_ `1`'_s is **strictly longer** than the **longest** contiguous segment of_ `0`'_s in_ `s`, or return `false` _otherwise_.

* For example, in `s = "110100010"` the longest continuous segment of `1`s has length `2`, and the longest continuous segment of `0`s has length `3`.

Note that if there are no `0`'s, then the longest continuous segment of `0`'s is considered to have a length `0`. The same applies if there is no `1`'s.

**Example 1:**

**Input:** s = "1101"
**Output:** true
**Explanation:**
The longest contiguous segment of 1s has length 2: "1101"
The longest contiguous segment of 0s has length 1: "1101"
The segment of 1s is longer, so return true.

**Example 2:**

**Input:** s = "111000"
**Output:** false
**Explanation:**
The longest contiguous segment of 1s has length 3: "111000"
The longest contiguous segment of 0s has length 3: "111000"
The segment of 1s is not longer, so return false.

**Example 3:**

**Input:** s = "110100010"
**Output:** false
**Explanation:**
The longest contiguous segment of 1s has length 2: "110100010"
The longest contiguous segment of 0s has length 3: "110100010"
The segment of 1s is not longer, so return false.

**Constraints:**

* `1 <= s.length <= 100`
* `s[i]` is either `'0'` or `'1'`.

# Approaches
## Brute-Force Substring Check
This approach directly translates the problem statement into code by checking every possible contiguous substring. It iterates through all possible start and end points, and for each resulting substring, it verifies if it consists of only '1's or only '0's. It keeps track of the maximum lengths found for both types of segments and compares them at the end.
**Time:** O(n^3), where n is the length of the string. There are three nested loops, each potentially running up to n times. · **Space:** O(1) extra space, as we only use a few variables to store counts and indices.
**Pros:** Conceptually straightforward and easy to derive from the problem definition.
**Cons:** Extremely inefficient due to its O(n^3) time complexity.; Performs many redundant checks on overlapping substrings.; Likely to time out on platforms with stricter time limits, although it may pass given the small constraint (n <= 100).
### Explanation
The brute-force method systematically explores all substrings of the input string `s`. It uses two nested loops to define the boundaries of a substring, with the outer loop for the starting index `i` and the inner loop for the ending index `j`. For each substring `s[i...j]`, a third loop is used to iterate through its characters to determine if it's a homogeneous segment of '1's or '0's. Two variables, `maxOnes` and `maxZeros`, are maintained to store the maximum lengths encountered. If a valid segment is found, its length is compared with the current maximum, and the maximum is updated if necessary. Finally, after examining all O(n^2) substrings, the method returns whether the longest segment of '1's is strictly longer than the longest segment of '0's.

```java
class Solution {
    public boolean checkOnesSegment(String s) {
        int maxOnes = 0;
        int maxZeros = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check segment from i to j
                boolean allOnes = true;
                boolean allZeros = true;
                for (int k = i; k <= j; k++) {
                    if (s.charAt(k) == '0') {
                        allOnes = false;
                    }
                    if (s.charAt(k) == '1') {
                        allZeros = false;
                    }
                }
                if (allOnes) {
                    maxOnes = Math.max(maxOnes, j - i + 1);
                }
                if (allZeros) {
                    maxZeros = Math.max(maxZeros, j - i + 1);
                }
            }
        }
        return maxOnes > maxZeros;
    }
}
```
### Algorithm
- Initialize `maxOnes` and `maxZeros` to 0.
- Use a nested loop structure to iterate through all possible start (`i`) and end (`j`) indices of substrings.
- For each substring defined by `i` and `j`, use a third loop (`k`) to verify if it's composed entirely of '1's or '0's.
- If a substring from `i` to `j` is all '1's, update `maxOnes = Math.max(maxOnes, j - i + 1)`.
- If it's all '0's, update `maxZeros = Math.max(maxZeros, j - i + 1)`.
- After all substrings have been checked, return the result of `maxOnes > maxZeros`.

## Single Pass Iteration
A much more efficient solution is to iterate through the string a single time. By maintaining a running count of the current contiguous '1's and '0's, we can find the longest segment of each in one pass. This avoids the redundant computations of the brute-force approach.
**Time:** O(n), where n is the length of the string `s`. We perform a single pass through the string. · **Space:** O(1) extra space. We only use a constant number of variables regardless of the input string's size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; The implementation is simple, clean, and easy to understand.
**Cons:** There are no significant disadvantages to this approach as it is optimal for the problem.
### Explanation
This optimal approach involves a single linear scan of the string. We use two variables, `currentOnes` and `currentZeros`, to keep track of the length of the current contiguous segment of '1's and '0's, respectively. We also use two other variables, `maxOnes` and `maxZeros`, to store the maximum length found so far for each digit.

As we iterate through the string, if we encounter a '1', we increment `currentOnes` and reset `currentZeros` to zero, because any ongoing segment of '0's is now broken. Conversely, if we see a '0', we increment `currentZeros` and reset `currentOnes`. After each character, we update `maxOnes` and `maxZeros` to ensure they hold the largest segment lengths seen up to that point. After the single pass is complete, a simple comparison of `maxOnes` and `maxZeros` gives the answer.

```java
class Solution {
    public boolean checkOnesSegment(String s) {
        int maxOnes = 0;
        int maxZeros = 0;
        int currentOnes = 0;
        int currentZeros = 0;

        for (char c : s.toCharArray()) {
            if (c == '1') {
                currentOnes++;
                currentZeros = 0; // Reset the count for the other digit
            } else { // c == '0'
                currentZeros++;
                currentOnes = 0; // Reset the count for the other digit
            }
            maxOnes = Math.max(maxOnes, currentOnes);
            maxZeros = Math.max(maxZeros, currentZeros);
        }

        return maxOnes > maxZeros;
    }
}
```
### Algorithm
- Initialize four integer variables: `maxOnes = 0`, `maxZeros = 0`, `currentOnes = 0`, `currentZeros = 0`.
- Iterate through the input string `s` character by character.
- If the current character is '1':
  - Increment `currentOnes`.
  - Reset `currentZeros` to 0.
- If the current character is '0':
  - Increment `currentZeros`.
  - Reset `currentOnes` to 0.
- After processing each character, update the maximums: `maxOnes = Math.max(maxOnes, currentOnes)` and `maxZeros = Math.max(maxZeros, currentZeros)`.
- After the loop completes, return the boolean result of `maxOnes > maxZeros`.