Watch 10 video solutions for Longer Contiguous Segments of Ones than Zeros, a easy level problem involving String. This walkthrough by Ayushi Rawat has 912 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |