1869. Longer Contiguous Segments of Ones than Zeros Solution

The problem

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

For example, in s = "110100010" the longest continuous segment of 1s has length 2, and the longest continuous segment of 0s has length 3.

Note that if there are no 0's, then the longest continuous segment of 0's is considered to have a length 0. The same applies if there is no 1's.

Example 1:

Input: s = "1101"
Output: true
Explanation:
The longest contiguous segment of 1s has length 2: "1101"
The longest contiguous segment of 0s has length 1: "1101"
The segment of 1s is longer, so return true.

Example 2:

Input: s = "111000"
Output: false
Explanation:
The longest contiguous segment of 1s has length 3: "111000"
The longest contiguous segment of 0s has length 3: "111000"
The segment of 1s is not longer, so return false.

Example 3:

Input: s = "110100010"
Output: false
Explanation:
The longest contiguous segment of 1s has length 2: "110100010"
The longest contiguous segment of 0s has length 3: "110100010"
The segment of 1s is not longer, so return false.

Constraints:

1 <= s.length <= 100
s[i] is either '0' or '1'.

Approach overview

Problem Overview: You get a binary string s. The task is to check whether the longest contiguous segment of '1' is strictly longer than the longest contiguous segment of '0'. The string must be scanned and the maximum run length for both characters compared.

Approach 1: Two-Pointer / Linear Scan (O(n) time, O(1) space)

This approach walks through the string once and counts the length of each contiguous segment. Maintain two variables: maxOnes and maxZeros. Use a pointer to iterate through the string and track the current streak length while the character stays the same. When the character changes, update the corresponding maximum and reset the counter. The key insight is that you only care about segment lengths, not their positions. Since each character is processed exactly once, the algorithm runs in O(n) time with constant O(1) space.

This is essentially a classic contiguous-run problem commonly seen with string processing and two pointers. It avoids storing segments or performing extra scans, which keeps the implementation short and interview‑friendly.

Approach 2: Dynamic Programming Style Tracking (O(n) time, O(n) space)

A dynamic programming interpretation tracks the length of the current streak ending at each index. Create arrays (or variables) that represent the length of consecutive '1' or '0' segments ending at position i. If the current character matches the previous one, extend the streak from i-1; otherwise start a new streak of length 1. While updating these values, maintain global maximums for both characters.

This approach is conceptually similar to many dynamic programming problems where the state depends on the previous element. It is less space‑efficient because it may store intermediate values for each index, but it clearly illustrates how segment lengths build incrementally across the string.

Recommended for interviews: The two-pointer linear scan is the expected solution. Interviewers want to see that you recognize this as a contiguous segment counting problem and solve it with a single pass. A DP formulation works but adds unnecessary memory overhead. Showing the single-pass approach demonstrates strong pattern recognition and efficient reasoning about strings.

Approach 1: Two-Pointer Approach

This approach involves using a two-pointer technique to traverse the string while counting consecutive '1's and '0's. We move through the string, checking each character:

If the character is the same as the last one, increment the current length counter.
Otherwise, compare the current length with the recorded maximum for the last sequence, then reset the current length for the new sequence.
Finally, after the loop, compare and return whether the longest sequence of '1's is greater than the longest sequence of '0's.

Python

def check_longest_segment(s):
    max1, max0, current = 0, 0, 1
    last = s[0]
    for char in s[1:]:
        if char == last:
            current += 1
        else:
            if last == '1':
                max1 = max(max1, current)
            else:
                max0 = max(max0, current)
            last = char
            current = 1
    if last == '1':
        max1 = max(max1, current)
    else:
        max0 = max(max0, current)
    return max1 > max0

# Test cases
print(check_longest_segment("1101"))  # Output: True
print(check_longest_segment("111000"))  # Output: False
print(check_longest_segment("110100010"))  # Output: False

Java

public class Main {
    public static boolean checkLongestSegment(String s) {
        int max1 = 0, max0 = 0, current = 1;
        char last = s.charAt(0);
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == last) {
                current++;
            } else {
                if (last == '1') {
                    max1 = Math.max(max1, current);
                } else {
                    max0 = Math.max(max0, current);
                }
                last = s.charAt(i);
                current = 1;
            }
        }
        if (last == '1') {
            max1 = Math.max(max1, current);
        } else {
            max0 = Math.max(max0, current);
        }
        return max1 > max0;
    }

    public static void main(String[] args) {
        System.out.println(checkLongestSegment("1101")); // Output: true
        System.out.println(checkLongestSegment("111000")); // Output: false
        System.out.println(checkLongestSegment("110100010")); // Output: false
    }
}

C++

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

bool checkLongestSegment(const string& s) {
    int max1 = 0, max0 = 0, current = 1;
    char last = s[0];
    for (size_t i = 1; i < s.length(); ++i) {
        if (s[i] == last) {
            current++;
        } else {
            if (last == '1') {
                if (current > max1) max1 = current;
            } else {
                if (current > max0) max0 = current;
            }
            last = s[i];
            current = 1;
        }
    }
    if (last == '1') {
        if (current > max1) max1 = current;
    } else {
        if (current > max0) max0 = current;
    }
    return max1 > max0;
}

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

JavaScript

function checkLongestSegment(s) {
    let max1 = 0, max0 = 0, current = 1;
    let last = s[0];
    for (let i = 1; i < s.length; i++) {
        if (s[i] === last) {
            current++;
        } else {
            if (last === '1') {
                max1 = Math.max(max1, current);
            } else {
                max0 = Math.max(max0, current);
            }
            last = s[i];
            current = 1;
        }
    }
    if (last === '1') {
        max1 = Math.max(max1, current);
    } else {
        max0 = Math.max(max0, current);
    }
    return max1 > max0;
}

console.log(checkLongestSegment("1101")); // Output: true
console.log(checkLongestSegment("111000")); // Output: false
console.log(checkLongestSegment("110100010")); // Output: false

#include <stdio.h>
#include <string.h>

int checkLongestSegment(char* s) {
    int max1 = 0, max0 = 0, current = 1;
    char last = s[0];
    for (int i = 1; i < strlen(s); i++) {
        if (s[i] == last) {
            current++;
        } else {
            if (last == '1') {
                if (current > max1) max1 = current;
            } else {
                if (current > max0) max0 = current;
            }
            last = s[i];
            current = 1;
        }
    }
    if (last == '1') {
        if (current > max1) max1 = current;
    } else {
        if (current > max0) max0 = current;
    }
    return max1 > max0;
}

int main() {
    printf("%d\n", checkLongestSegment("1101")); // Output: 1 (true)
    printf("%d\n", checkLongestSegment("111000")); // Output: 0 (false)
    printf("%d\n", checkLongestSegment("110100010")); // Output: 0 (false)
    return 0;
}

using System;

public class Solution {
    public bool CheckLongestSegment(string s) {
        int max1 = 0, max0 = 0, current = 1;
        char last = s[0];
        for (int i = 1; i < s.Length; i++) {
            if (s[i] == last) {
                current++;
            } else {
                if (last == '1') {
                    max1 = Math.Max(max1, current);
                } else {
                    max0 = Math.Max(max0, current);
                }
                last = s[i];
                current = 1;
            }
        }
        if (last == '1') {
            max1 = Math.Max(max1, current);
        } else {
            max0 = Math.Max(max0, current);
        }
        return max1 > max0;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.CheckLongestSegment("1101")); // Output: true
        Console.WriteLine(sol.CheckLongestSegment("111000")); // Output: false
        Console.WriteLine(sol.CheckLongestSegment("110100010")); // Output: false
    }
}

In this Python solution, a for loop iterates through the string starting from the second character. It checks current sequence lengths and updates maximums for '1's and '0's. The final output is a boolean comparing the longest sequences.

Complexity

Time complexity is O(n) and space complexity is O(1). This is due to using a few integer variables and processing the string in a single pass.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

In this dynamic programming (DP) approach, we create state arrays to store the maximum lengths of segments ending at each index. Then, by evaluating combinations of '0's and '1's, we update these DP arrays:

Initialize two arrays, one for '1's and one for '0's, to keep track of the longest contiguous segment ending at each index.
Iterate over the string indices, updating the arrays based on the character at the current position.
At each step, use previous values from the DP arrays to build up solutions to reach maximum segment lengths.
At the end of the iteration, the solution depends on comparing the largest values in the '1' and '0' arrays.

Python

def check_longest_segment_dp(s):
    dp1 = [0] * len(s)
    dp0 = [0] * len(s)

    if s[0] == '1':
        dp1[0] = 1
    else:
        dp0[0] = 1

    for i in range(1, len(s)):
        if s[i] == '1':
            dp1[i] = dp1[i-1] + 1
            dp0[i] = 0
        else:
            dp0[i] = dp0[i-1] + 1
            dp1[i] = 0

    return max(dp1) > max(dp0)

# Test cases
print(check_longest_segment_dp("1101"))  # Output: True
print(check_longest_segment_dp("111000"))  # Output: False
print(check_longest_segment_dp("110100010"))  # Output: False

JavaScript

function checkLongestSegmentDP(s) {
    let dp1 = Array(s.length).fill(0);
    let dp0 = Array(s.length).fill(0);

    if (s[0] === '1') {
        dp1[0] = 1;
    } else {
        dp0[0] = 1;
    }

    for (let i = 1; i < s.length; i++) {
        if (s[i] === '1') {
            dp1[i] = dp1[i-1] + 1;
        } else {
            dp0[i] = dp0[i-1] + 1;
        }
    }

    const max1 = Math.max(...dp1);
    const max0 = Math.max(...dp0);

    return max1 > max0;
}

console.log(checkLongestSegmentDP("1101")); // Output: true
console.log(checkLongestSegmentDP("111000")); // Output: false
console.log(checkLongestSegmentDP("110100010")); // Output: false

This Python solution uses dynamic programming with two arrays to store the lengths of continuous segments of '1's and '0's ending at each index. The result is then derived from comparing the maximum values from these arrays, indicating which segment is longest.

Complexity

Time complexity is O(n) with an O(n) space complexity due to storing state arrays for segment lengths.

Try this approach in the editor

Approach 3: Two Passes

We design a function f(x), which represents the length of the longest consecutive substring in string s composed of x. If f(1) > f(0), then return true, otherwise return false.

The time complexity is O(n), where n is the length of the string s. The space complexity is $O(1)`.

TypeScript

function checkZeroOnes(s: string): boolean {
    const f = (x: string): number => {
        let [mx, cnt] = [0, 0];
        for (const c of s) {
            if (c === x) {
                mx = Math.max(mx, ++cnt);
            } else {
                cnt = 0;
            }
        }
        return mx;
    };
    return f('1') > f('0');
}

func checkZeroOnes(s string) bool {
	f := func(x rune) int {
		cnt, mx := 0, 0
		for _, c := range s {
			if c == x {
				cnt++
				mx = max(mx, cnt)
			} else {
				cnt = 0
			}
		}
		return mx
	}
	return f('1') > f('0')
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Approach	Time complexity is O(n) and space complexity is O(1). This is due to using a few integer variables and processing the string in a single pass.
Dynamic Programming Approach	Time complexity is O(n) with an O(n) space complexity due to storing state arrays for segment lengths.
Two Passes	–

Complexity analysis

Approach	Time	Space	When to Use
Two-Pointer / Linear Scan	O(n)	O(1)	Best general solution. Single pass with constant memory, ideal for interviews and production code.
Dynamic Programming Tracking	O(n)	O(n)	Useful for learning DP state transitions or when explicitly storing streak lengths per index.

Frequently asked questions

Is Longer Contiguous Segments of Ones than Zeros easy or hard?

LeetCode classifies this problem as Easy. It focuses on recognizing contiguous segments in a binary string and implementing a simple linear scan. The main challenge is correctly updating streak counts and maximum values during iteration.

Longer Contiguous Segments of Ones than Zeros Python/Java solution

In both Python and Java, iterate through the string while tracking the current streak length and two maximum values for '1' and '0'. Update the maximum whenever a streak ends. The logic is identical across languages and runs in O(n) time with constant extra space.

How to solve Longer Contiguous Segments of Ones than Zeros in O(n)?

Iterate through the string and maintain a counter for the current streak of identical characters. When the character changes, update either the maximum ones segment or maximum zeros segment. Reset the streak counter and continue scanning. After processing the string, check if maxOnes > maxZeros.

What is the best approach for Longer Contiguous Segments of Ones than Zeros?

The best approach is a single-pass linear scan using a two-pointer or streak-counting technique. Track the length of the current contiguous segment and update the maximum lengths for '1' and '0'. After scanning the string once, compare the two maximum values. This solution runs in O(n) time and O(1) space.

Is Longer Contiguous Segments of Ones than Zeros asked at Google/Amazon/Meta?

This problem represents a common string traversal and contiguous segment pattern frequently asked in coding interviews. Variants of run-length counting and streak detection appear in interviews at companies like Amazon, Google, and Meta when testing string manipulation fundamentals.

What data structure is used in Longer Contiguous Segments of Ones than Zeros?

The solution mainly uses simple variables and counters while scanning the string. No advanced data structures are required. The problem falls under string processing and two-pointer traversal patterns.

What is the time complexity of Longer Contiguous Segments of Ones than Zeros?

The optimal algorithm runs in O(n) time where n is the length of the binary string. Each character is visited exactly once while counting contiguous segments. Space complexity is O(1) because only a few counters are maintained.

Longer Contiguous Segments of Ones than Zeros solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Approach

Approach 2: Dynamic Programming Approach

Approach 3: Two Passes

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longer Contiguous Segments of Ones than Zeros solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Approach

Approach 2: Dynamic Programming Approach

Approach 3: Two Passes

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems