1869. Longer Contiguous Segments of Ones than Zeros
Problem Description
The problem presents us with a binary string s
, which consists only of 0
s and 1
s. Our goal is to determine whether the longest sequence of consecutive 1
s is longer than the longest sequence of consecutive 0
s in the binary string. If the longest sequence of 1
s is longer, we should return true
; otherwise, we return false
. A sequence of consecutive 1
s or 0
s means they are directly next to each other without being interrupted by the other digit.
For example, let's take a binary string s = "110100010"
. Here, the longest segment of 1
s has length 2
, and the longest segment of 0
s has a length of 3
. So in this case, the function should return false
because the segment of 0
s is longer than the segment of 1
s.
If there are no 0
s in the string, the length of the longest segment of 0
s is 0
, and similarly, if there are no 1
s, the length of the longest segment of 1
s is 0
.
Intuition
The algorithm needs to go through the string s
and track the length of the current segment of consecutive 1
s and 0
s, as well as the length of the longest segments found so far. The idea is to iterate through the string once and, for each character:
- If the character is a
0
, we increase the temporary count of0
s (t0
) by 1 and reset the temporary count for1
s (t1
) to 0 because the sequence of1
s is interrupted. - Similarly, if the character is a
1
, we do the opposite: increase the count for1
s and reset the count for0
s.
While performing these operations, we also keep track of the maximum lengths seen so far for both 0
s and 1
s. This is done by comparing the current temporary counts (t0
and t1
) with the max counts (n0
and n1
) respectively and updating the max counts if the current is greater.
At the end of the iteration, we simply compare the longest segment of 1
s to the longest segment of 0
s and return true
if the segment of 1
s is longer; otherwise, we return false
.
This solution is efficient because it only requires a single pass through the string, making it a linear time algorithm with O(n) complexity, where n is the length of the string.
Solution Approach
The solution to the "Check if Binary String Has at Most One Segment of Ones" problem relies on an approach that allows us to find the longest contiguous segments of 1
s and 0
s in a single pass through the string.
Here is a step-by-step walkthrough of the implementation from the provided solution code:
-
Initialize four variables:
n0
andn1
are set to 0 to keep track of the maximum lengths of the segments of0
s and1
s respectively;t0
andt1
are set to 0 to keep the count of the current length of the segments of0
s and1
s. -
Iterate through each character
c
in the binary strings
:- If
c
is'0'
, increment the count oft0
because we are in a segment of0
s, and resett1
to 0 as we're no longer in a segment of1
s. - If
c
is'1'
, increment the count oft1
because we are in a segment of1
s, and resett0
to 0 as we're no longer in a segment of0
s.
- If
-
After every iteration (for each character
c
), refresh the maximum valuesn0
andn1
by comparing them witht0
andt1
. This ensures that after processing the complete string,n0
andn1
hold the lengths of the longest segments of0
s and1
s, respectively.- Update
n0
by evaluatingn0 = max(n0, t0)
. - Update
n1
by evaluatingn1 = max(n1, t1)
.
- Update
-
Finally, once the iteration is finished, return the result of comparing
n1
andn0
by returningTrue
ifn1 > n0
andFalse
otherwise. This comparison dictates whether the longest contiguous segment of1
s is strictly longer than the longest contiguous segment of0
s.
No additional data structures or complex patterns are needed for the implementation. The efficiency lies in the simplicity of using counting variables and updating maximums, which only employ basic operations.
The algorithm, thus, performs in O(n) time complexity, where n is the length of the binary string, because it requires just one scan through the string. The space complexity is O(1), as the amount of extra space used does not grow with the size of the input.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider a small example with the binary string s = "0110011"
. When this string is passed through the algorithm described in the solution approach, here's a step-by-step explanation of what happens:
-
Initialize variables:
n0 = 0
,n1 = 0
to keep track of the maximum lengths of0
s and1
s, andt0 = 0
,t1 = 0
to keep track of the current lengths. -
Iteration starts:
c = '0'
:t0
becomes 1,t1
is reset to 0. We comparen0
witht0
, nown0=1
andn1=0
.c = '1'
:t1
becomes 1,t0
is reset to 0. Sincen1
(which is 0) is less thant1
(which is 1), we updaten1=1
. Nown0=1
andn1=1
.c = '1'
:t1
increases to 2,t0
remains 0. Updaten1
to 2, as it is greater than the currentn1
. Nown0=1
andn1=2
.c = '0'
:t0
becomes 1,t1
is reset to 0, do not updaten0
orn1
as current values oft0
andt1
are not greater thann0
andn1
.c = '0'
:t0
increases to 2,t1
remains 0. Updaten0
to 2, as it is equal to the currentt0
. Nown0=2
andn1=2
.c = '1'
:t1
becomes 1,t0
is reset to 0. Do not updaten0
orn1
.c = '1'
:t1
increases to 2,t0
remains 0. Do not updaten1
ast1
equalsn1
. Final values aren0=2
andn1=2
.
-
Once the iteration is over, we compare
n1
andn0
. Sincen1
is not greater thann0
, we returnFalse
.
No segment of 1
s is strictly longer than the longest segment of 0
s in the binary string s = "0110011"
, so our algorithm correctly returns False
based on the provided method. The complexity remains linear since we only went through the string a single time, and the space complexity is constant as we only kept track of a fixed number of variables.
Solution Implementation
1class Solution:
2 def checkZeroOnes(self, s: str) -> bool:
3 # Initialize variables to keep track of the longest consecutive sequence of '0's and '1's
4 max_zeros = max_ones = 0
5 current_zeros = current_ones = 0
6
7 # Iterate over the characters in the string
8 for char in s:
9 if char == '0':
10 # Increase the sequence count of '0's, reset the sequence of '1's
11 current_zeros += 1
12 current_ones = 0
13 else:
14 # Do the opposite when we encounter '1's
15 current_zeros = 0
16 current_ones += 1
17
18 # Update the maximum sequence lengths for '0's and '1's
19 max_zeros = max(max_zeros, current_zeros)
20 max_ones = max(max_ones, current_ones)
21
22 # Check if the maximum sequence of '1's is greater than that of '0's
23 return max_ones > max_zeros
24
1class Solution {
2 public boolean checkZeroOnes(String s) {
3 int longestZeroSeq = 0; // Variable to track the length of the longest contiguous sequence of '0's
4 int longestOneSeq = 0; // Variable to track the length of the longest contiguous sequence of '1's
5 int currentZeroSeq = 0; // Variable to track the length of the current contiguous sequence of '0's
6 int currentOneSeq = 0; // Variable to track the length of the current contiguous sequence of '1's
7
8 // Iterate over each character in the string
9 for (int i = 0; i < s.length(); ++i) {
10 if (s.charAt(i) == '0') { // If the current character is '0'
11 currentZeroSeq++; // Increase the length of the current '0' sequence
12 currentOneSeq = 0; // Reset the length of the '1' sequence
13 } else { // If the current character is '1'
14 currentOneSeq++; // Increase the length of the current '1' sequence
15 currentZeroSeq = 0; // Reset the length of the '0' sequence
16 }
17 // Update the longest sequence lengths if the current sequences are longer
18 longestZeroSeq = Math.max(longestZeroSeq, currentZeroSeq);
19 longestOneSeq = Math.max(longestOneSeq, currentOneSeq);
20 }
21
22 // After going through the string, check if the longest sequence of '1's is strictly greater than '0's
23 return longestOneSeq > longestZeroSeq;
24 }
25}
26
1class Solution {
2public:
3 // Function to check if the longest continuous sequence of 1s is longer than the longest continuous sequence of 0s
4 bool checkZeroOnes(string s) {
5 int longestZero = 0; // Stores the length of the longest sequence of '0's
6 int longestOne = 0; // Stores the length of the longest sequence of '1's
7 int currentZero = 0; // Tracks the current sequence length of '0's
8 int currentOne = 0; // Tracks the current sequence length of '1's
9
10 // Loop through the input string character by character
11 for (char c : s) {
12 if (c == '0') {
13 // If the current character is '0', increase the count of the current sequence of '0's
14 ++currentZero;
15 // Reset the current sequence of '1's since it's interrupted by a '0'
16 currentOne = 0;
17 } else { // c is '1'
18 // If the current character is '1', increase the count of the current sequence of '1's
19 ++currentOne;
20 // Reset the current sequence of '0's since it's interrupted by a '1'
21 currentZero = 0;
22 }
23
24 // Update the longest sequence length of '0's if necessary
25 longestZero = max(longestZero, currentZero);
26 // Update the longest sequence length of '1's if necessary
27 longestOne = max(longestOne, currentOne);
28 }
29
30 // Return true if the longest sequence of '1's is greater than the longest sequence of '0's
31 return longestOne > longestZero;
32 }
33};
34
1/**
2 * Determines if the longest contiguous segment of 1s is longer than the
3 * longest contiguous segment of 0s in the binary string.
4 *
5 * @param {string} s - A binary string containing only '0's and '1's.
6 * @return {boolean} - True if the longest segment of 1s is longer than
7 * the longest segment of 0s; otherwise, false.
8 */
9const checkZeroOnes = (s: string): boolean => {
10 let maxZeros: number = 0; // Tracks the length of the longest segment of 0s.
11 let maxOnes: number = 0; // Tracks the length of the longest segment of 1s.
12 let currentZeros: number = 0; // Tracks the length of the current segment of 0s.
13 let currentOnes: number = 0; // Tracks the length of the current segment of 1s.
14
15 for (let char of s) {
16 if (char === '0') {
17 currentZeros++; // Increment the count of contiguous 0s.
18 currentOnes = 0; // Reset the count of contiguous 1s.
19 } else {
20 currentOnes++; // Increment the count of contiguous 1s.
21 currentZeros = 0; // Reset the count of contiguous 0s.
22 }
23
24 // Update the maximum counts if the current counts are greater.
25 maxZeros = Math.max(maxZeros, currentZeros);
26 maxOnes = Math.max(maxOnes, currentOnes);
27 }
28 // Return true if longest segment of 1s is longer than longest segment of 0s.
29 return maxOnes > maxZeros;
30};
31
32// The function can be used as follows:
33// const result: boolean = checkZeroOnes("11001");
34// console.log(result); // Output would be true if the longest segment of 1s is longer than the longest segment of 0s.
35
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the length of the input string s
. This is because the code consists of a single for-loop that iterates over each character in the string exactly once.
During each iteration, the code does a constant amount of work: updating counters t0
and t1
, resetting one counter depending on the character, and calculating the maximum length of consecutive '0's and '1's seen so far using max()
. Since all these operations are constant time, the loop represents a linear time complexity relative to the length of the string.
The space complexity of the code is O(1)
. The amount of extra space used by the algorithm does not depend on the size of the input string. The variables n0
, n1
, t0
, and t1
use a fixed amount of space. No additional space that grows with input size is required. Therefore, the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!