Longer Contiguous Segments of Ones than Zeros

Difficulty: Easy | Acceptance: 62.50% | Paid: No Topics: String

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 contiguous segment of 1’s has length 2, and the longest contiguous segment of 0’s has length 3. So, we return false.

• Examples
• Constraints
• Single Pass
• Split and Compare
• Two Pass

Examples

Input: s = "1101"
Output: true
Explanation: The longest contiguous segment of 1's has length 2, and the longest contiguous segment of 0's has length 1.

Input: s = "111000"
Output: false
Explanation: The longest contiguous segment of 1's has length 3, and the longest contiguous segment of 0's has length 3.

Input: s = "110100010"
Output: false
Explanation: The longest contiguous segment of 1's has length 2, and the longest contiguous segment of 0's has length 3.

Constraints

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

Single Pass

Intuition Traverse the string once while tracking the current run length of consecutive 1s and 0s, updating the maximum lengths seen so far.

Steps

• Initialize variables to track maximum and current run lengths for both 1s and 0s
• Iterate through each character in the string
• If character is ‘1’, increment current 1s run and reset current 0s run, update max 1s
• If character is ‘0’, increment current 0s run and reset current 1s run, update max 0s
• Return whether max 1s is strictly greater than max 0s

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        max_ones = max_zeros = 0
        curr_ones = curr_zeros = 0
        
        for c in s:
            if c == '1':
                curr_ones += 1
                curr_zeros = 0
                max_ones = max(max_ones, curr_ones)
            else:
                curr_zeros += 1
                curr_ones = 0
                max_zeros = max(max_zeros, curr_zeros)
        
        return max_ones > max_zeros

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) only using constant extra space
• Notes: Most efficient approach with single traversal

Split and Compare

Intuition Split the string by ‘0’ to get all segments of 1s, and split by ‘1’ to get all segments of 0s, then compare the maximum lengths.

Steps

• Split the string by ‘0’ to get an array of 1s segments
• Split the string by ‘1’ to get an array of 0s segments
• Find the maximum length among 1s segments
• Find the maximum length among 0s segments
• Return whether max 1s length is strictly greater than max 0s length

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones_segments = s.split('0')
        zeros_segments = s.split('1')
        
        max_ones = max(len(seg) for seg in ones_segments) if ones_segments else 0
        max_zeros = max(len(seg) for seg in zeros_segments) if zeros_segments else 0
        
        return max_ones > max_zeros

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for storing split segments
• Notes: More readable but uses extra space for split arrays

Two Pass

Intuition Make two separate passes through the string - first to find the longest segment of 1s, then to find the longest segment of 0s.

Steps

• Define a helper function to find the longest contiguous segment of a given character
• First pass: find the longest segment of ‘1’s
• Second pass: find the longest segment of ‘0’s
• Return whether the longest 1s segment is strictly longer than the longest 0s segment

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        def max_segment(char):
            max_len = 0
            curr_len = 0
            for c in s:
                if c == char:
                    curr_len += 1
                    max_len = max(max_len, curr_len)
                else:
                    curr_len = 0
            return max_len
        
        return max_segment('1') > max_segment('0')

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) only using constant extra space
• Notes: Clean code with helper function, but traverses string twice