Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1869. Longer Contiguous Segments of Ones than Zeros - Leetcode Solution

Code Implementation

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        max_ones = max_zeros = 0
        current = s[0]
        count = 1

        for i in range(1, len(s)):
            if s[i] == current:
                count += 1
            else:
                if current == '1':
                    max_ones = max(max_ones, count)
                else:
                    max_zeros = max(max_zeros, count)
                current = s[i]
                count = 1
        # Final segment
        if current == '1':
            max_ones = max(max_ones, count)
        else:
            max_zeros = max(max_zeros, count)
        return max_ones > max_zeros
      
class Solution {
public:
    bool checkZeroOnes(string s) {
        int maxOnes = 0, maxZeros = 0;
        char current = s[0];
        int count = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == current) {
                ++count;
            } else {
                if (current == '1')
                    maxOnes = max(maxOnes, count);
                else
                    maxZeros = max(maxZeros, count);
                current = s[i];
                count = 1;
            }
        }
        if (current == '1')
            maxOnes = max(maxOnes, count);
        else
            maxZeros = max(maxZeros, count);
        return maxOnes > maxZeros;
    }
};
      
class Solution {
    public boolean checkZeroOnes(String s) {
        int maxOnes = 0, maxZeros = 0;
        char current = s.charAt(0);
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == current) {
                count++;
            } else {
                if (current == '1')
                    maxOnes = Math.max(maxOnes, count);
                else
                    maxZeros = Math.max(maxZeros, count);
                current = s.charAt(i);
                count = 1;
            }
        }
        if (current == '1')
            maxOnes = Math.max(maxOnes, count);
        else
            maxZeros = Math.max(maxZeros, count);
        return maxOnes > maxZeros;
    }
}
      
var checkZeroOnes = function(s) {
    let maxOnes = 0, maxZeros = 0;
    let current = s[0], count = 1;
    for (let i = 1; i < s.length; i++) {
        if (s[i] === current) {
            count++;
        } else {
            if (current === '1')
                maxOnes = Math.max(maxOnes, count);
            else
                maxZeros = Math.max(maxZeros, count);
            current = s[i];
            count = 1;
        }
    }
    if (current === '1')
        maxOnes = Math.max(maxOnes, count);
    else
        maxZeros = Math.max(maxZeros, count);
    return maxOnes > maxZeros;
};

Problem Description

Given a binary string s (a string consisting only of the characters '0' and '1'), determine whether the longest contiguous segment of '1's is strictly longer than the longest contiguous segment of '0's. Return true if this is the case, and false otherwise.
  • There is only one valid answer for each input.
  • Each segment must be contiguous (i.e., consecutive characters).
  • You cannot reuse elements between segments; segments must be non-overlapping.

Thought Process

The key to solving this problem is realizing that you only need to compare the lengths of the longest runs (segments) of consecutive '1's and '0's. You don't need to count the total number of '1's or '0's, just the length of their longest contiguous segments. A brute-force approach would be to check every possible substring, but that's inefficient. Instead, we can scan the string once, keeping track of the current run's character and length, and updating the maximum lengths as we go. This is similar to counting the longest streak of heads or tails when flipping a coin: you only care about the maximum consecutive streak for each side.

Solution Approach

To solve the problem efficiently, we use a single pass through the string, tracking the length of the current segment and updating the maximums as needed.
  1. Initialize two variables, one for the maximum length of '1's (max_ones) and one for '0's (max_zeros).
  2. Start from the first character, and keep a counter for the current segment's length (count), as well as the current character (current).
  3. Iterate through the string from the second character onward:
    • If the current character matches the previous, increment count.
    • If it differs, update the appropriate max variable (max_ones or max_zeros) with count if it's larger, then reset count to 1 and update current to the new character.
  4. After the loop, don't forget to update the maximum for the last segment (since the string may end with the longest segment).
  5. Finally, compare max_ones and max_zeros and return whether max_ones is greater.
This approach is efficient because it only requires a single pass through the string and constant extra space.

Example Walkthrough

Let's consider the input s = "1101":
  • Start with current = '1', count = 1.
  • Index 1: s[1] = '1' (same as current), increment count to 2.
  • Index 2: s[2] = '0' (different), update max_ones = 2, set current = '0', count = 1.
  • Index 3: s[3] = '1' (different), update max_zeros = 1, set current = '1', count = 1.
  • End of string: update max_ones = 2 (since last segment is '1's of length 1, which is not greater than previous max).
Final values: max_ones = 2, max_zeros = 1. Since 2 > 1, return true.

Time and Space Complexity

  • Brute-force approach: If you checked every possible substring, it would be O(n2) time and O(1) space, which is inefficient for large strings.
  • Optimized approach (used here): The algorithm scans the string once, so it runs in O(n) time, where n is the length of the string. It uses a constant number of variables, so space complexity is O(1).

Summary

The problem asks us to compare the longest contiguous segments of '1's and '0's in a binary string. By iterating through the string once and keeping counters for the current and maximum segment lengths, we can efficiently solve the problem in linear time and constant space. The key insight is to focus on segment lengths, not total counts, and to update the maximums as we encounter changes in the character sequence.