algoadvance

You are given a binary string s that consists only of zeros and ones. Return true if the longest contiguous segment of ones is strictly longer than the longest contiguous segment of zeros in the binary string. Return false otherwise.

Clarifying Questions

  1. What is the length of the input string s?
    • Constraints: ( 1 \leq \text{len}(s) \leq 1000 ).
  2. Is the input string guaranteed to be non-empty?
    • Yes, according to the constraints.
  3. Can the input have only zeros or only ones?
    • Yes, the input can be entirely zeros or entirely ones.

Strategy

  1. Initialize variables:
    • max_ones to track the maximum length of contiguous ones segment.
    • max_zeros to track the maximum length of contiguous zeros segment.
    • current_ones and current_zeros to track the current length of contiguous segments while traversing the string.
  2. Traverse the string from left to right:
    • If the character is ‘1’, increment current_ones and reset current_zeros to zero.
    • If the character is ‘0’, increment current_zeros and reset current_ones to zero.
    • After updating counters for each character, update max_ones and max_zeros accordingly.
  3. Compare the max_ones and max_zeros:
    • Return True if max_ones is greater than max_zeros, otherwise return False.

Time Complexity

Code

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

By following these steps, the solution efficiently determines whether the longest contiguous segment of ones is strictly longer than the longest contiguous segment of zeros.

Try our interview co-pilot at AlgoAdvance.com