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.
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 <= 100s[i] is either '0' or '1'.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.
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:
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.
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.
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:
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.
Python
JavaScript
Time complexity is O(n) with an O(n) space complexity due to storing state arrays for segment lengths.
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)`.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| 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 | — |
| 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. |
1869. Longer Contiguous Segments of Ones than Zeros | Leetcode weekly contest | Ayushi Rawat • Ayushi Rawat • 912 views views
Watch 9 more video solutions →Practice Longer Contiguous Segments of Ones than Zeros with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor