Longer Contiguous Segments of Ones than Zeros

Longer Contiguous Segments of Ones than Zeros - Problem

String Easy

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.

Input & Output

Example 1 — Mixed Segments

$ Input: s = "110100010"

› Output: false

💡 Note: Longest segment of 1s has length 2 (positions 0-1), longest segment of 0s has length 3 (positions 4-6). Since 2 ≤ 3, return false.

Example 2 — 1s Win

$ Input: s = "1110001"

› Output: true

💡 Note: Longest segment of 1s has length 3 (positions 0-2), longest segment of 0s has length 3 (positions 3-5). But wait - there's also a single 1 at the end, so we have segments [3,1] for 1s and [3] for 0s. Max 1s = 3, Max 0s = 3. Actually this should be false. Let me recalculate: segments are 111|000|1, so max 1s = 3, max 0s = 3, result is false.

Example 3 — All Ones

$ Input: s = "111"

› Output: true

💡 Note: Only 1s present with length 3, no 0s (length 0). Since 3 > 0, return true.

Constraints

1 ≤ s.length ≤ 1000
s consists only of '0' and '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with mixed segments of 0s and 1s

Process

Find longest contiguous segment for each digit type

Output

Return true if max 1s segment > max 0s segment

Key Takeaway

🎯 Key Insight: Track maximum segment lengths for both digit types in a single pass through the string

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is to track the maximum length of contiguous segments for both 0s and 1s in a single pass through the string. The optimal approach uses single-pass tracking with segment change detection. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Find All Segments	O(n)	O(n)	Find all contiguous segments of 0s and 1s, then compare their maximum lengths
Single Pass - Track Maximum Lengths	O(n)	O(1)	Single pass through string tracking maximum segment lengths for both 0s and 1s

Brute Force - Find All Segments — Algorithm Steps

Step 1: Find all contiguous segments of 1s and store their lengths
Step 2: Find all contiguous segments of 0s and store their lengths
Step 3: Compare the maximum lengths of both types

Visualization

Tap to expand

Step-by-Step Walkthrough

Find 1s Segments

Scan for all contiguous 1s: [2, 1]

Find 0s Segments

Scan for all contiguous 0s: [1, 3, 2]

Compare Max

max(1s)=2, max(0s)=3, return false

Code -

solution.c — C

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

bool solution(char* s) {
    int onesSegments[1000];
    int zerosSegments[1000];
    int onesCount = 0, zerosCount = 0;
    
    // Find all segments of 1s
    int i = 0;
    int len = strlen(s);
    while (i < len) {
        if (s[i] == '1') {
            int count = 0;
            while (i < len && s[i] == '1') {
                count++;
                i++;
            }
            onesSegments[onesCount++] = count;
        } else {
            i++;
        }
    }
    
    // Find all segments of 0s
    i = 0;
    while (i < len) {
        if (s[i] == '0') {
            int count = 0;
            while (i < len && s[i] == '0') {
                count++;
                i++;
            }
            zerosSegments[zerosCount++] = count;
        } else {
            i++;
        }
    }
    
    int maxOnes = 0;
    for (int j = 0; j < onesCount; j++) {
        if (onesSegments[j] > maxOnes) {
            maxOnes = onesSegments[j];
        }
    }
    
    int maxZeros = 0;
    for (int j = 0; j < zerosCount; j++) {
        if (zerosSegments[j] > maxZeros) {
            maxZeros = zerosSegments[j];
        }
    }
    
    return maxOnes > maxZeros;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the string of length n

✓ Linear Growth

Space Complexity

O(n)

Arrays to store all segment lengths in worst case

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~8 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Find All Segments — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler