2609. Find the Longest Balanced Substring of a Binary String

EasyString
Leetcode Link

Problem Description

Given a binary string s which contains only the characters '0' and '1', the task is to find the length of the longest substring where two conditions are satisfied:

  1. All the zeros in the substring must come before any ones.
  2. The quantity of zeros must equal the quantity of ones within the substring.

These conditions define a "balanced" substring. This includes the consideration that an empty substring (one with no characters at all) is also balanced. A substring is simply any sequence of consecutive characters from the original string.

To summarize: you need to find a contiguous sequence within the given binary string where there is an equal number of zeros and ones, and all zeros precede the ones.

Intuition

Approaching this problem, one could initially think of a brute force strategy, trying every possible substring of s to check if it is balanced and keeping track of the longest one. However, this method proves inefficient with a time complexity of O(n^3), where n is the length of the string s.

An optimized strategy is to traverse the string while tracking the number of continuous zeros and ones. For every new character, there are certain things to be done based on whether it is a zero or a one:

  • If it's a '0', and if we have already encountered a '1', both the count of zeros and ones need to be reset since a balanced substring cannot have zeros after ones. If no '1' has been encountered (one is zero), simply increment the count of zeros, since we might be extending a balanced substring.

  • If it's a '1', increment the count of ones. Since a balanced substring must have equal numbers of zeros and ones, we update the maximum length of a balanced substring using the minimum of the current counts of zeros and ones, multiplied by 2 (to account for both zeros and ones).

This way, we can traverse the string only once, updating the count of zeros and ones and the maximum balanced substring length as we go. This improved method significantly reduces the time complexity to O(n) with a constant space complexity, as there are no additional data structures used to keep track of potential substrings.

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

Which of these properties could exist for a graph but not a tree?

Solution Approach

The provided solution efficiently finds the longest balanced substring using the following approach:

  1. Initialize three variables: ans to keep track of the maximum length discovered so far, zero to count the consecutive zeros, and one to count the consecutive ones. All are initially set to 0.

  2. Traverse the string s character by character using a for loop. For each character c encountered:

    a. If c is '0': - Check if the count of ones is greater than 0. This indicates that we've previously encountered a '1', and since a balanced substring can't have a '0' after a '1', we must reset both zero and one. - After the check, or if no '1' has been encountered yet, increment the count of zeros (zero).

    b. If c is '1': - Simply increment the count of ones (one). - Calculate the length of potential balanced substring as 2 times the minimum of zero and one counts. The multiplication by 2 is necessary to account for both zeros and ones in the matching counts. - Update the ans with the higher value between its current value and the potential balanced substring length calculated.

  3. Continue the process until the whole string has been traversed.

  4. Return ans as the length of the longest balanced substring found.

By only using counters and traversing the string once, this solution effectively employs a single-pass algorithm. Since it avoids nested loops or extensive substring operations, it significantly optimizes the time taken compared to brute-force methods. No additional data structures beyond simple variables are used, offering the benefit of constant space complexity.

The method hinges on understanding the problem's constraints and recognizing that a balanced substring can always be identified by pairing zeros and ones as long as they are in sequence and in equal number.

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

Which data structure is used to implement recursion?

Example Walkthrough

Let's consider a small binary string s = "00110" to illustrate the solution approach.

Step 1: Initialize ans = 0, zero = 0, one = 0.

Step 2: Traverse the string character by character:

  • Index 0: Encounter '0'

    • zero becomes 1 (zero = 1), since one = 0 we continue.
    • ans remains 0.

  • Index 1: Encounter another '0'

    • zero increments to 2 (zero = 2).
    • ans remains 0.

  • Index 2: Encounter a '1'

    • one increments to 1 (one = 1).
    • Possible balanced substring length here is min(zero, one) * 2 = 2, so ans updates to 2.

  • Index 3: Encounter another '1'

    • one increments to 2 (one = 2).
    • Now we have an equal count of zeros and ones.
    • Possible balanced substring length is min(zero, one) * 2 = 4, so ans updates to 4.

  • Index 4: Encounter a '0'

    • Since we've previously encountered ones and now we see a '0', we reset both zero and one as this '0' cannot be part of a balanced substring following the encountered '1's.
    • zero resets to 1 (zero = 1), and one resets to 0 (one = 0).
    • ans remains 4, as no new balanced substring is found.

Step 3: Having traversed the string, we've completed our single pass.

Step 4: The final ans is 4. Hence, the longest balanced substring has a length of 4. In the given string "00110," the substring "0011" satisfies the conditions: equal number of zeros and ones, and all zeros come before any ones.

This walkthrough demonstrates how the algorithm processes each character of the input string, updating counters and maintaining the maximum length of a balanced substring as it progresses through the string. By doing so in a single pass, it achieves an efficient O(n) time complexity.

Solution Implementation

1class Solution:
2    def find_the_longest_balanced_substring(self, s: str) -> int:
3        # Initialize the longest balanced length, count of zeros and ones to zero
4        longest_balanced_length = zero_count = one_count = 0
5      
6        # Iterate over each character in the string
7        for char in s:
8            if char == '0':
9                # If we encounter a zero and there is an existing one count,
10                # reset both counts as we no longer have a balanced substring
11                if one_count:
12                    zero_count = one_count = 0
13                # Increment the zero count otherwise
14                zero_count += 1
15            else:  # Otherwise, char is '1'
16                # Increment the one count
17                one_count += 1
18                # Update the longest balanced length with the minimum count of zeros and ones
19                # multiplied by 2 (to count both zeros and ones)
20                longest_balanced_length = max(longest_balanced_length, 2 * min(one_count, zero_count))
21      
22        # Return the length of the longest balanced substring
23        return longest_balanced_length
24
1class Solution {
2    // This method finds and returns the length of the longest balanced substring containing equal numbers of '0's and '1's.
3    public int findTheLongestBalancedSubstring(String s) {
4        int countZero = 0; // Count of '0's seen so far
5        int countOne = 0;  // Count of '1's seen so far
6        int maxLength = 0; // Length of the longest balanced substring found so far
7        int n = s.length(); // Length of the input string
8
9        // Loop through each character in the string
10        for (int i = 0; i < n; ++i) {
11            // If the current character is a '0'
12            if (s.charAt(i) == '0') {
13                // If there were any '1's seen without a corresponding '0', reset both counts
14                if (countOne > 0) {
15                    countZero = 0;
16                    countOne = 0;
17                }
18                // Increment the count of '0's
19                ++countZero;
20            } else {
21                // If the current character is a '1', we attempt to form a balanced substring.
22                // Update maxLength to be the greater of its current value and twice the minimum of countZero and countOne+1.
23                // The increment on countOne is done inline within the comparison.
24                maxLength = Math.max(maxLength, 2 * Math.min(countZero, ++countOne));
25            }
26        }
27        return maxLength; // Return the length of the longest balanced substring
28    }
29}
30
1class Solution {
2public:
3    int findTheLongestBalancedSubstring(string s) {
4        int countZero = 0; // Initialize counter for '0's
5        int countOne = 0;  // Initialize counter for '1's
6        int maxLength = 0; // Store the maximum length of a balanced substring
7      
8        // Iterate through the string character by character
9        for (char& c : s) {
10            if (c == '0') {
11                // If we encounter a '0', then there can't be a balanced substring
12                // that starts before this point, so we reset the counters
13                if (countOne > 0) {
14                    countZero = 0;
15                    countOne = 0;
16                }
17                // Increment the counter for '0's
18                ++countZero;
19            } else { // c == '1'
20                // Increment the counter for '1's and update the maximum length
21                // The maximum length for a balanced substring is twice the minimum
22                // of countZero and countOne (since a balanced substring contains equal '0's and '1's)
23                maxLength = max(maxLength, 2 * min(countZero, ++countOne));
24            }
25        }
26      
27        return maxLength; // Return the maximum length found
28    }
29};
30
1function findTheLongestBalancedSubstring(s: string): number {
2    // Initialize counters for consecutive zeros and ones
3    let zeroCount = 0;
4    let oneCount = 0;
5
6    // Initialize the answer to store the maximum length of a balanced substring
7    let maxLength = 0;
8
9    // Iterate over each character in the string
10    for (const char of s) {
11        if (char === '0') {
12            // If a '0' is found and there are pending ones, reset the counts
13            if (oneCount > 0) {
14                zeroCount = 0;
15                oneCount = 0;
16            }
17            // Increment the count for zeros
18            ++zeroCount;
19        } else {
20            // On finding a '1', calculate the potential balanced substring length
21            // and update the maximum length if necessary
22            maxLength = Math.max(maxLength, 2 * Math.min(zeroCount, ++oneCount));
23        }
24    }
25
26    // Return the maximum balanced substring length found
27    return maxLength;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

How many times is a tree node visited in a depth first search?

Time and Space Complexity

The time complexity of the given code is O(n) because it consists of a single loop that iterates over each character in the input string s exactly once. The size of the input string is denoted by n, thus resulting in a linear relationship between the input size and the number of operations performed.

The space complexity is O(1) as the code uses only a constant amount of additional space that does not scale with the input size. The variables ans, zero, and one occupy a fixed amount of space regardless of the length of the string.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

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

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 👨‍🏫