Longer Contiguous Segments Of Ones Than Zeros - Leetcode Solution

Problem statement:

Given a binary string s, return True if the longest contiguous segment of 1s is strictly longer than the longest contiguous segment of 0s in s. Return False otherwise.

Example 1: Input: s = "1101" Output: true Explanation: The longest contiguous segment of 1s is "11". The longest contiguous segment of 0s is "0". The segment of 1s is longer than the segment of 0s.

Example 2: Input: s = "111000" Output: false Explanation: The longest contiguous segment of 1s is "111". The longest contiguous segment of 0s is "000". The segment of 1s is not longer than the segment of 0s.

Solution:

The solution to this problem can be solved using a simple approach where we traverse the given binary string s and keep track of the longest contiguous segment of 1s and 0s while doing so.

Given the binary string s, we initialize two variables oneCount and zeroCount to zero, and two variables maxOneCount and maxZeroCount to zero. We traverse the binary string s character by character, and if we encounter a '1', we increment oneCount and set zeroCount to zero. Similarly, if we encounter a '0', we increment zeroCount and set oneCount to zero.

While traversing, we also check the value of oneCount and zeroCount after each increment. If oneCount is greater than maxOneCount, we update maxOneCount to oneCount. Similarly, if zeroCount is greater than maxZeroCount, we update maxZeroCount to zeroCount.

Once we have traversed the entire binary string s, we check if maxOneCount is greater than maxZeroCount. If it is, we return True, else False.

The time complexity of this approach is O(n), where n is the length of the binary string s, and the space complexity is O(1).

Below is the Python implementation of the above approach:

def checkZeroOnes(s: str) -> bool: oneCount = 0 zeroCount = 0 maxOneCount = 0 maxZeroCount = 0

for c in s:
    if c == '1':
        oneCount += 1
        zeroCount = 0
    else:
        zeroCount += 1
        oneCount = 0
    
    if oneCount > maxOneCount:
        maxOneCount = oneCount
    
    if zeroCount > maxZeroCount:
        maxZeroCount = zeroCount

return maxOneCount > maxZeroCount

We can test the solution for both the given examples as follows:

print(checkZeroOnes("1101")) # Output: True print(checkZeroOnes("111000")) # Output: False

The output matches the expected output for both cases.

1