Skip to main content
Talentd

Longer Contiguous Segments of Ones than Zeros - Solution & Explanation

EasyString14 min read
Practice this problem

Problem Statement

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:

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

This C program implements a two-pointer technique to traverse the input string and determine the longest contiguous segments of '1's and '0's. It maintains counters for lengths and updates them as it finds longer segments. Finally, it compares the maximum lengths of segments of '1's and '0's and returns whether '1's are longer.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of this approach is O(n), where n is the length of the string. The space complexity is O(1) because it requires only a constant amount of space.

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:

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

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.

Code

PythonJavaScript

Python

JavaScript

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)`.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Approach

The time complexity of this approach is O(n), where n is the length of the string. The space complexity is O(1) because it requires only a constant amount of space.

Dynamic Programming Approach

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

Two Passes—

Detailed Complexity Analysis

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

Video Solution

1869. Longer Contiguous Segments of Ones than Zeros | Leetcode weekly contest | Ayushi Rawat • Ayushi Rawat • 915 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Longer Contiguous Segments of Ones than Zeros with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if Binary String Has at Most One Segment of Ones

Next

Count Subarrays With More Ones Than Zeros