algoadvance

Leetcode 1869. Longer Contiguous Segments of Ones than Zeros

Problem Statement

Given a binary string s, return true if the longest contiguous segment of ones is strictly longer than the longest contiguous segment of zeros in the string, or false otherwise.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the binary string s?
    • Are there any non-binary characters allowed in the string?
  2. Output Expectations:
    • Should the function return only a boolean value?
  3. Edge Cases:
    • What should be the output if the string is empty?
    • What should be the output if both longest segments of ones and zeros are equal?

Code

Based on the problem statement, let’s implement the solution in C++.

#include <iostream>
#include <string>
using namespace std;

bool checkZeroOnes(string s) {
    int maxOnes = 0, maxZeros = 0;
    int currentOnes = 0, currentZeros = 0;
    
    for (char c : s) {
        if (c == '1') {
            currentOnes++;
            currentZeros = 0;
        } else {
            currentZeros++;
            currentOnes = 0;
        }
        
        if (currentOnes > maxOnes) {
            maxOnes = currentOnes;
        }
        if (currentZeros > maxZeros) {
            maxZeros = currentZeros;
        }
    }
    
    return maxOnes > maxZeros;
}

int main() {
    // Test cases
    cout << checkZeroOnes("1101") << endl;  // Output: true
    cout << checkZeroOnes("111000") << endl;  // Output: false
    cout << checkZeroOnes("110100010") << endl;  // Output: false
    return 0;
}

Strategy

  1. Initialize Counters:
    • maxOnes and maxZeros to keep track of the maximum length of contiguous segments of ‘1’s and ‘0’s respectively.
    • currentOnes and currentZeros to count the current segment lengths of ‘1’s and ‘0’s respectively.
  2. Iterate through the String:
    • If the character is ‘1’, increment currentOnes and reset currentZeros to 0.
    • If the character is ‘0’, increment currentZeros and reset currentOnes to 0.
    • Update maxOnes and maxZeros whenever currentOnes or currentZeros exceed the recorded maximums.
  3. Comparison:
    • After processing the string, compare maxOnes and maxZeros to determine the result.

Time Complexity

The time complexity of this solution is O(n) where n is the length of the string:

The space complexity is O(1) because we are using a fixed amount of extra space for integer counters.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI