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 <= 100s[i] is either '0' or '1'
Hints for Longer Contiguous Segments of Ones than Zeros
Hint 1
Measure every maximal run of equal characters.
Hint 2
Keep two maxima: one for runs of 1s, one for runs of 0s.
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
- Set
best[0] = best[1] = 0andrun = 0. - For each index
i:run = run + 1ifs[i] == s[i-1], otherwiserun = 1. - Update
best[s[i]] = max(best[s[i]], run). - 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