1869. Longer Contiguous Segments of Ones than Zeros

EasyString
Leetcode Link

Problem Description

The problem presents us with a binary string s, which consists only of 0s and 1s. Our goal is to determine whether the longest sequence of consecutive 1s is longer than the longest sequence of consecutive 0s in the binary string. If the longest sequence of 1s is longer, we should return true; otherwise, we return false. A sequence of consecutive 1s or 0s 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 1s has length 2, and the longest segment of 0s has a length of 3. So in this case, the function should return false because the segment of 0s is longer than the segment of 1s.

If there are no 0s in the string, the length of the longest segment of 0s is 0, and similarly, if there are no 1s, the length of the longest segment of 1s is 0.

Intuition

The algorithm needs to go through the string s and track the length of the current segment of consecutive 1s and 0s, 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 of 0s (t0) by 1 and reset the temporary count for 1s (t1) to 0 because the sequence of 1s is interrupted.
  • Similarly, if the character is a 1, we do the opposite: increase the count for 1s and reset the count for 0s.

While performing these operations, we also keep track of the maximum lengths seen so far for both 0s and 1s. 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 1s to the longest segment of 0s and return true if the segment of 1s 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the maximum element can be found in:

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 1s and 0s in a single pass through the string.

Here is a step-by-step walkthrough of the implementation from the provided solution code:

  1. Initialize four variables: n0 and n1 are set to 0 to keep track of the maximum lengths of the segments of 0s and 1s respectively; t0 and t1 are set to 0 to keep the count of the current length of the segments of 0s and 1s.

  2. Iterate through each character c in the binary string s:

    • If c is '0', increment the count of t0 because we are in a segment of 0s, and reset t1 to 0 as we're no longer in a segment of 1s.
    • If c is '1', increment the count of t1 because we are in a segment of 1s, and reset t0 to 0 as we're no longer in a segment of 0s.

  3. After every iteration (for each character c), refresh the maximum values n0 and n1 by comparing them with t0 and t1. This ensures that after processing the complete string, n0 and n1 hold the lengths of the longest segments of 0s and 1s, respectively.

    • Update n0 by evaluating n0 = max(n0, t0).
    • Update n1 by evaluating n1 = max(n1, t1).

  4. Finally, once the iteration is finished, return the result of comparing n1 and n0 by returning True if n1 > n0 and False otherwise. This comparison dictates whether the longest contiguous segment of 1s is strictly longer than the longest contiguous segment of 0s.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example 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:

  1. Initialize variables: n0 = 0, n1 = 0 to keep track of the maximum lengths of 0s and 1s, and t0 = 0, t1 = 0 to keep track of the current lengths.

  2. Iteration starts:

    • c = '0': t0 becomes 1, t1 is reset to 0. We compare n0 with t0, now n0=1 and n1=0.
    • c = '1': t1 becomes 1, t0 is reset to 0. Since n1 (which is 0) is less than t1 (which is 1), we update n1=1. Now n0=1 and n1=1.
    • c = '1': t1 increases to 2, t0 remains 0. Update n1 to 2, as it is greater than the current n1. Now n0=1 and n1=2.
    • c = '0': t0 becomes 1, t1 is reset to 0, do not update n0 or n1 as current values of t0 and t1 are not greater than n0 and n1.
    • c = '0': t0 increases to 2, t1 remains 0. Update n0 to 2, as it is equal to the current t0. Now n0=2 and n1=2.
    • c = '1': t1 becomes 1, t0 is reset to 0. Do not update n0 or n1.
    • c = '1': t1 increases to 2, t0 remains 0. Do not update n1 as t1 equals n1. Final values are n0=2 and n1=2.

  3. Once the iteration is over, we compare n1 and n0. Since n1 is not greater than n0, we return False.

No segment of 1s is strictly longer than the longest segment of 0s 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
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫