Longer Contiguous Segments of Ones than Zeros

Easy
1189.

Longer Contiguous Segments of Ones than Zeros

Longer Contiguous Segments of Ones than Zeros is an easy coding problem on strings and counting, asked in Amazon and Microsoft interviews.

s is a binary string. Return true if its longest contiguous segment of 1s is strictly longer than its longest contiguous segment of 0s, and false otherwise.

If s has no 0s, its longest segment of 0s has length 0; likewise for 1s.

Example 1

Input
s = "11100110"
Output
true
Explanation
The longest run of 1s has length 3, of 0s length 2.

Example 2

Input
s = "111000"
Output
false
Explanation
Both longest runs have length 3.

Example 3

Input
s = "0"
Output
false

Constraints

  • 1 <= s.length <= 100
  • s[i] is either '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var checkZeroOnes = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longer Contiguous Segments of Ones than Zeros — Solution

Longer Contiguous Segments of Ones than Zeros solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Longer Contiguous Segments of Ones than Zeros is an easy coding problem on strings and counting, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, Counting
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

s is a binary string. Return true if its longest contiguous segment of 1s is strictly longer than its longest contiguous segment of 0s, and false otherwise.

If s has no 0s, its longest segment of 0s has length 0; likewise for 1s.

Example 1

Input: s = "11100110"
Output: true
Explanation: The longest run of 1s has length 3, of 0s length 2.

Example 2

Input: s = "111000"
Output: false
Explanation: Both longest runs have length 3.

Example 3

Input: s = "0"
Output: false

Constraints

  • 1 <= s.length <= 100
  • s[i] is either '0' or '1'

Hints for Longer Contiguous Segments of Ones than Zeros

  1. Hint 1

    Measure every maximal run of equal characters.

  2. Hint 2

    Keep two maxima: one for runs of 1s, one for runs of 0s.

  3. Hint 3

    Compare them at the end with a strict >.

How to solve Longer Contiguous Segments of Ones than Zeros

One scan measures every run of equal characters; record the longest run separately for each of the two characters and compare.

Approach

  1. Set best[0] = best[1] = 0 and run = 0.
  2. For each index i: run = run + 1 if s[i] == s[i-1], otherwise run = 1.
  3. Update best[s[i]] = max(best[s[i]], run).
  4. Return best[1] > best[0].

Why it works

The running counter equals the length of the run ending at i, so the maximum over all i with s[i] == c is the length of the longest run of c. A character that never appears keeps its maximum at 0, as the statement requires.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The comparison is strict — equal lengths give false.
  • Update the maximum during the scan so the final run is not forgotten.

Reference solution

Python

def checkZeroOnes(s: str) -> bool:
    best = [0, 0]
    run = 0
    for i, c in enumerate(s):
        run = run + 1 if i > 0 and s[i - 1] == c else 1
        b = 1 if c == '1' else 0
        best[b] = max(best[b], run)
    return best[1] > best[0]

Java

public static boolean checkZeroOnes(String s) {
    int[] best = new int[2];
    int run = 0;
    for (int i = 0; i < s.length(); i++) {
        run = (i > 0 && s.charAt(i) == s.charAt(i - 1)) ? run + 1 : 1;
        int b = s.charAt(i) - '0';
        best[b] = Math.max(best[b], run);
    }
    return best[1] > best[0];
}

C++

bool checkZeroOnes(string s) {
    int best[2] = {0, 0};
    int run = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        run = (i > 0 && s[i] == s[i - 1]) ? run + 1 : 1;
        int b = s[i] - '0';
        best[b] = max(best[b], run);
    }
    return best[1] > best[0];
}

JavaScript

var checkZeroOnes = function(s) {
    var best = [0, 0];
    var run = 0;
    for (var i = 0; i < s.length; i++) {
        run = (i > 0 && s[i] === s[i - 1]) ? run + 1 : 1;
        var b = s[i] === "1" ? 1 : 0;
        if (run > best[b]) best[b] = run;
    }
    return best[1] > best[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings