Scale Engineer

Longer Contiguous Segments of Ones than Zeros

Easy
#1707Time: O(n^3), where n is the length of the string. There are three nested loops, each potentially running up to n times.Space: O(1) extra space, as we only use a few variables to store counts and indices.
Data structures
String

Prompt

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'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code by checking every possible contiguous substring. It iterates through all possible start and end points, and for each resulting substring, it verifies if it consists of only '1's or only '0's. It keeps track of the maximum lengths found for both types of segments and compares them at the end.

Algorithm

  • Initialize maxOnes and maxZeros to 0.
  • Use a nested loop structure to iterate through all possible start (i) and end (j) indices of substrings.
  • For each substring defined by i and j, use a third loop (k) to verify if it's composed entirely of '1's or '0's.
  • If a substring from i to j is all '1's, update maxOnes = Math.max(maxOnes, j - i + 1).
  • If it's all '0's, update maxZeros = Math.max(maxZeros, j - i + 1).
  • After all substrings have been checked, return the result of maxOnes > maxZeros.

Walkthrough

The brute-force method systematically explores all substrings of the input string s. It uses two nested loops to define the boundaries of a substring, with the outer loop for the starting index i and the inner loop for the ending index j. For each substring s[i...j], a third loop is used to iterate through its characters to determine if it's a homogeneous segment of '1's or '0's. Two variables, maxOnes and maxZeros, are maintained to store the maximum lengths encountered. If a valid segment is found, its length is compared with the current maximum, and the maximum is updated if necessary. Finally, after examining all O(n^2) substrings, the method returns whether the longest segment of '1's is strictly longer than the longest segment of '0's.

class Solution {    public boolean checkOnesSegment(String s) {        int maxOnes = 0;        int maxZeros = 0;        int n = s.length();         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Check segment from i to j                boolean allOnes = true;                boolean allZeros = true;                for (int k = i; k <= j; k++) {                    if (s.charAt(k) == '0') {                        allOnes = false;                    }                    if (s.charAt(k) == '1') {                        allZeros = false;                    }                }                if (allOnes) {                    maxOnes = Math.max(maxOnes, j - i + 1);                }                if (allZeros) {                    maxZeros = Math.max(maxZeros, j - i + 1);                }            }        }        return maxOnes > maxZeros;    }}

Complexity

Time

O(n^3), where n is the length of the string. There are three nested loops, each potentially running up to n times.

Space

O(1) extra space, as we only use a few variables to store counts and indices.

Trade-offs

Pros

  • Conceptually straightforward and easy to derive from the problem definition.

Cons

  • Extremely inefficient due to its O(n^3) time complexity.

  • Performs many redundant checks on overlapping substrings.

  • Likely to time out on platforms with stricter time limits, although it may pass given the small constraint (n <= 100).

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem