Problem

Given a binary string s, return true _if thelongest contiguous segment of _1’_s isstrictly longer than the longest contiguous segment of _0’s ins, or return false otherwise.

  • For example, in s = "_11_ 01 _000_ 10" the longest continuous segment of 1s has length 2, and the longest continuous segment of 0s 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.

Examples

Example 1

1
2
3
4
5
6

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

Example 2

1
2
3
4
5
6

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

Example 3

1
2
3
4
5
6

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

Constraints

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

Solution

Method 1 – Single Pass Segment Counting (1)

Intuition

We can find the longest contiguous segment of ‘1’s and ‘0’s by scanning the string once and keeping track of the current and maximum segment lengths for both characters.

Approach

  1. Initialize variables to track the current and maximum segment lengths for ‘1’ and ‘0’.
  2. Iterate through the string:
    • If the current character is the same as the previous, increment the current segment length.
    • Otherwise, reset the current segment length to 1.
    • Update the maximum segment length for ‘1’ or ‘0’ as needed.
  3. After the loop, compare the maximum segment lengths of ‘1’ and ‘0’.
  4. Return true if the maximum segment of ‘1’s is strictly longer than that of ‘0’s, else false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool checkZeroOnes(string s) {
        int max1 = 0, max0 = 0, cur = 1;
        for (int i = 1; i <= s.size(); ++i) {
            if (i < s.size() && s[i] == s[i-1]) cur++;
            else {
                if (s[i-1] == '1') max1 = max(max1, cur);
                else max0 = max(max0, cur);
                cur = 1;
            }
        }
        return max1 > max0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func checkZeroOnes(s string) bool {
    max1, max0, cur := 0, 0, 1
    for i := 1; i <= len(s); i++ {
        if i < len(s) && s[i] == s[i-1] {
            cur++
        } else {
            if s[i-1] == '1' {
                if cur > max1 { max1 = cur }
            } else {
                if cur > max0 { max0 = cur }
            }
            cur = 1
        }
    }
    return max1 > max0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public boolean checkZeroOnes(String s) {
        int max1 = 0, max0 = 0, cur = 1;
        for (int i = 1; i <= s.length(); i++) {
            if (i < s.length() && s.charAt(i) == s.charAt(i-1)) cur++;
            else {
                if (s.charAt(i-1) == '1') max1 = Math.max(max1, cur);
                else max0 = Math.max(max0, cur);
                cur = 1;
            }
        }
        return max1 > max0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun checkZeroOnes(s: String): Boolean {
        var max1 = 0; var max0 = 0; var cur = 1
        for (i in 1..s.length) {
            if (i < s.length && s[i] == s[i-1]) cur++
            else {
                if (s[i-1] == '1') max1 = maxOf(max1, cur)
                else max0 = maxOf(max0, cur)
                cur = 1
            }
        }
        return max1 > max0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        max1 = max0 = cur = 1
        for i in range(1, len(s)+1):
            if i < len(s) and s[i] == s[i-1]:
                cur += 1
            else:
                if s[i-1] == '1':
                    max1 = max(max1, cur)
                else:
                    max0 = max(max0, cur)
                cur = 1
        return max1 > max0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn check_zero_ones(s: String) -> bool {
        let s = s.as_bytes();
        let (mut max1, mut max0, mut cur) = (0, 0, 1);
        for i in 1..=s.len() {
            if i < s.len() && s[i] == s[i-1] {
                cur += 1;
            } else {
                if s[i-1] == b'1' {
                    max1 = max1.max(cur);
                } else {
                    max0 = max0.max(cur);
                }
                cur = 1;
            }
        }
        max1 > max0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    checkZeroOnes(s: string): boolean {
        let max1 = 0, max0 = 0, cur = 1;
        for (let i = 1; i <= s.length; i++) {
            if (i < s.length && s[i] === s[i-1]) cur++;
            else {
                if (s[i-1] === '1') max1 = Math.max(max1, cur);
                else max0 = Math.max(max0, cur);
                cur = 1;
            }
        }
        return max1 > max0;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. We scan the string once.
  • 🧺 Space complexity: O(1), only a few variables are used.