LeetCode 1869 - Longer Contiguous Segments of Ones than Zeros

LeetCode Problem 1869

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a binary string s, which means the string contains only the characters '0' and '1'. We need to determine whether the longest contiguous sequence of 1s is strictly longer than the longest contiguous sequence of 0s.

A contiguous segment means consecutive characters without interruption. For example, in the string "1110011":

• The longest segment of 1s is "111", which has length 3
• The longest segment of 0s is "00", which has length 2

Since 3 > 2, the answer would be true.

The key detail is that we only care about the maximum length for each character type. We do not care how many segments exist overall. We only compare:

• longest run of 1s
• longest run of 0s

The problem guarantees:

• 1 <= s.length <= 100
• every character is either '0' or '1'

Because the input size is very small, even inefficient solutions would work. However, the goal is still to design a clean and optimal linear-time solution.

There are several important edge cases to consider:

• A string containing only 1s, such as "1111"
• A string containing only 0s, such as "0000"
• Alternating characters like "101010"
• Equal maximum lengths such as "111000"
• Very short strings of length 1

A naive implementation can easily make mistakes when transitioning between segments or when updating the maximum lengths at the end of the string.

Approaches

Brute Force Approach

A brute-force solution would examine every possible substring and determine whether it consists entirely of 0s or entirely of 1s. While scanning these substrings, we could track the longest valid segment for each character.

For a string of length n, there are O(n²) substrings. Checking whether each substring is made entirely of one repeated character could take up to O(n) time. This leads to a total complexity of O(n³).

Even though n <= 100, making this approach technically feasible, it is unnecessarily inefficient because the problem only requires identifying consecutive runs, which can be done in a single pass.

Optimal Approach

The key observation is that contiguous segments naturally appear while scanning the string from left to right.

Instead of checking every substring, we can:

• Track the current character segment length
• Reset the count whenever the character changes
• Maintain the maximum segment length for 0s and 1s separately

This works because every contiguous segment is encountered exactly once during a linear scan.

As we iterate through the string:

• If the current character matches the previous character, we extend the current segment
• Otherwise, we start a new segment of length 1
• After updating the current segment length, we update the appropriate maximum

At the end, we simply compare the two maximum values.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks all substrings and validates segments
Optimal	O(n)	O(1)	Single linear scan tracking contiguous runs

Algorithm Walkthrough

1. Initialize four variables:

• max_ones to store the longest segment of 1s
• max_zeros to store the longest segment of 0s
• current_length to track the current segment size
• previous_char to remember the last character seen

2. Start iterating through the string from left to right.
3. For each character:

• If it matches the previous character, increment current_length
• Otherwise, reset current_length to 1 because a new segment begins

4. Depending on whether the current character is '1' or '0':

• Update max_ones
• Or update max_zeros

5. Update previous_char to the current character so the next iteration can compare against it.
6. After processing the entire string, compare:

• max_ones > max_zeros

7. Return the result of that comparison.

Why it works

The algorithm maintains the invariant that current_length always represents the length of the current contiguous segment ending at the current index.

Every time a segment grows, we update the corresponding maximum value. Since every character is processed exactly once, every contiguous segment is considered exactly once. Therefore, the final maximum values correctly represent the longest segments of 1s and 0s.

Python Solution

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        max_ones = 0
        max_zeros = 0

        current_length = 0
        previous_char = ""

        for char in s:
            if char == previous_char:
                current_length += 1
            else:
                current_length = 1

            if char == '1':
                max_ones = max(max_ones, current_length)
            else:
                max_zeros = max(max_zeros, current_length)

            previous_char = char

        return max_ones > max_zeros

The implementation begins by initializing the maximum segment lengths for both 1s and 0s. These variables will store the best segment lengths seen so far.

The variable current_length tracks the size of the current contiguous segment. The variable previous_char helps determine whether the current segment continues or a new one begins.

During iteration:

• If the current character matches the previous one, the segment continues and the length increases.
• Otherwise, a new segment starts with length 1.

After updating the segment length, the code updates either max_ones or max_zeros depending on the current character.

Finally, the function returns whether the longest segment of 1s is strictly larger than the longest segment of 0s.

Go Solution

func checkZeroOnes(s string) bool {
    maxOnes := 0
    maxZeros := 0

    currentLength := 0
    previousChar := byte(0)

    for i := 0; i < len(s); i++ {
        if s[i] == previousChar {
            currentLength++
        } else {
            currentLength = 1
        }

        if s[i] == '1' {
            if currentLength > maxOnes {
                maxOnes = currentLength
            }
        } else {
            if currentLength > maxZeros {
                maxZeros = currentLength
            }
        }

        previousChar = s[i]
    }

    return maxOnes > maxZeros
}

The Go implementation follows exactly the same logic as the Python solution. Since Go strings are byte arrays for ASCII characters, we access characters using indexing like s[i].

The variable previousChar is initialized with byte(0), which does not match either '0' or '1'. This guarantees the first character starts a new segment correctly.

Go does not provide a built-in max function for integers in older versions, so the implementation uses explicit comparisons when updating maximum values.

Worked Examples

Example 1

Input:

s = "1101"

Index	Character	Previous	Current Length	Max Ones	Max Zeros
0	1	none	1	1	0
1	1	1	2	2	0
2	0	1	1	2	1
3	1	0	1	2	1

Final comparison:

2 > 1

Result:

true

Example 2

Input:

s = "111000"

Index	Character	Previous	Current Length	Max Ones	Max Zeros
0	1	none	1	1	0
1	1	1	2	2	0
2	1	1	3	3	0
3	0	1	1	3	1
4	0	0	2	3	2
5	0	0	3	3	3

Final comparison:

3 > 3

Result:

false

Example 3

Input:

s = "110100010"

Index	Character	Previous	Current Length	Max Ones	Max Zeros
0	1	none	1	1	0
1	1	1	2	2	0
2	0	1	1	2	1
3	1	0	1	2	1
4	0	1	1	2	1
5	0	0	2	2	2
6	0	0	3	2	3
7	1	0	1	2	3
8	0	1	1	2	3

Final comparison:

2 > 3

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a fixed number of variables are used

The algorithm performs a single linear scan through the string. No auxiliary data structures are required, and memory usage remains constant regardless of input size.

Test Cases

solution = Solution()

assert solution.checkZeroOnes("1101") == True      # longer ones segment
assert solution.checkZeroOnes("111000") == False   # equal segment lengths
assert solution.checkZeroOnes("110100010") == False  # longer zero segment

assert solution.checkZeroOnes("1") == True         # single one
assert solution.checkZeroOnes("0") == False        # single zero

assert solution.checkZeroOnes("11111") == True     # only ones
assert solution.checkZeroOnes("00000") == False    # only zeros

assert solution.checkZeroOnes("1010101") == False  # alternating pattern

assert solution.checkZeroOnes("11110") == True     # large ones block
assert solution.checkZeroOnes("100001") == False   # large zeros block

assert solution.checkZeroOnes("110011111000") == True  # longest ones wins
assert solution.checkZeroOnes("11110000") == False     # equal large blocks

Test	Why
"1101"	Basic example where ones win
"111000"	Equal maximum segment lengths
"110100010"	Zeros have longer segment
"1"	Minimum size with only ones
"0"	Minimum size with only zeros
"11111"	Entire string is ones
"00000"	Entire string is zeros
"1010101"	Alternating characters
"11110"	Large ones segment near start
"100001"	Large zeros segment in middle
"110011111000"	Longer ones segment later in string
"11110000"	Equal large segments

Edge Cases

One important edge case is when the string contains only one type of character. For example, "11111" contains no zeros at all. A buggy implementation might incorrectly assume both character types always appear. In this solution, max_zeros simply remains 0, which correctly reflects the problem statement.

Another important case is alternating characters such as "101010". Every contiguous segment has length 1, so both maximum values remain 1. Since the problem requires the ones segment to be strictly longer, the algorithm correctly returns false.

A third edge case occurs when the longest segments are equal, such as "111000". Some implementations mistakenly use >= instead of >. This solution explicitly checks max_ones > max_zeros, ensuring equality returns false exactly as required.

A final subtle case is the first character in the string. Since there is no previous character yet, the implementation must properly initialize the first segment length. The solution handles this by resetting current_length to 1 whenever the character changes, including the very first iteration.