Jobs

Interviews

Discussions

Find the Longest Balanced Substring of a Binary String

Easy

Asked by:

9 views

Topics:

Strings

You are given a binary string s consisting only of zeroes and ones.

A substring of s is considered balanced if all zeroes are before ones and the number of zeroes is equal to the number of ones inside the substring. Notice that the empty substring is considered a balanced substring.

Return the length of the longest balanced substring of s.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "01000111"
Output: 6
Explanation: The longest balanced substring is "000111", which has length 6.

Example 2:

Input: s = "00111"
Output: 4
Explanation: The longest balanced substring is "0011", which has length 4.

Example 3:

Input: s = "111"
Output: 0
Explanation: There is no balanced substring except the empty substring, so the answer is 0.

Constraints:

1 <= s.length <= 50
'0' <= s[i] <= '1'

Try coding it in LeetCode

Find the Longest Balanced Substring of a Binary String

Easy

Asked by:

9 views

Topics:

Strings

You are given a binary string s consisting only of zeroes and ones.

Return the length of the longest balanced substring of s.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "01000111"
Output: 6
Explanation: The longest balanced substring is "000111", which has length 6.

Example 2:

Input: s = "00111"
Output: 4
Explanation: The longest balanced substring is "0011", which has length 4.

Example 3:

Input: s = "111"
Output: 0
Explanation: There is no balanced substring except the empty substring, so the answer is 0.

Constraints:

1 <= s.length <= 50
'0' <= s[i] <= '1'

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the binary string?
What should I return if the input string is empty or null?
By 'balanced', do you mean the substring must contain an equal number of '0's and '1's?
If there are multiple balanced substrings of the same maximum length, should I return any one of them, or is there a specific criteria to choose one?
Can the input string contain characters other than '0' and '1'?

Brute Force Solution

Approach

The brute force approach checks every possible part of the binary string to see if it's balanced. We consider all possible substrings, one by one, to find the longest one that satisfies the balance requirement. We are trying everything to find the answer.

Here's how the algorithm would work step-by-step:

Start by looking at the very first character of the string.
Then, consider the first two characters, then the first three, and so on, all the way to the end of the string.
For each of these 'substrings' (parts of the string), check if the number of zeros is equal to the number of ones.
If the number of zeros and ones are equal, remember the length of this substring.
Now, move to the second character of the string, and repeat the same process: look at the substring starting at the second character with length one, then two, then three, and so on.
Keep doing this, moving the starting point of the substring one character at a time, until you reach the end of the string.
As you check each substring, always remember the length of the longest balanced substring you've found so far.
After checking every possible substring, the longest balanced substring you remembered is your answer.

Code Implementation

def find_longest_balanced_substring_brute_force(binary_string):
    longest_balanced_substring_length = 0

    string_length = len(binary_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            substring = binary_string[start_index:end_index + 1]
            substring_length = len(substring)

            zeros_count = 0
            ones_count = 0

            for char in substring:
                if char == '0':
                    zeros_count += 1
                else:
                    ones_count += 1

            # Check if the current substring is balanced.
            if zeros_count == ones_count:

                # Update max length if current substring is longer
                if substring_length > longest_balanced_substring_length:
                    longest_balanced_substring_length = substring_length

    return longest_balanced_substring_length

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible substrings of the binary string. The outer loop iterates n times, defining the starting index of the substring. The inner loop iterates up to n times, defining the length of the substring. For each substring, we count the number of zeros and ones, which takes up to n operations. Therefore, the time complexity is O(n * n * n), which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach iterates through all possible substrings of the input binary string. The algorithm only uses a few integer variables to store the current substring's start and end indices, and counters for zeros and ones to check if the substring is balanced, and a variable to keep track of the maximum length seen so far. The amount of memory used by these variables is constant and does not depend on the size of the input string N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find the longest part of a string that has an equal number of zeros and ones. Instead of checking every possible part, we can cleverly track how far we are from having a balanced substring, and quickly identify when a longer balanced substring appears by remembering where we've seen certain patterns before.

Here's how the algorithm would work step-by-step:

Imagine each '0' we see adds +1 to a counter and each '1' subtracts -1 from the counter.
As we go through the string, keep track of the first time each counter value appears. We can use a dictionary or similar tool for this.
If we encounter a counter value we've seen before, it means the section of the string between those two occurrences has an equal number of zeros and ones (it's balanced!).
Calculate the length of this balanced substring.
Keep updating the longest balanced substring found so far as we move through the string.
If the counter is zero, that means all the characters seen so far are balanced, and it could be the longest such substring.

Code Implementation

def find_longest_balanced_substring(binary_string):
    counter = 0
    first_occurrence = {0: -1}
    max_length = 0

    for i, bit in enumerate(binary_string):
        if bit == '0':
            counter += 1
        else:
            counter -= 1

        # Check if this counter value has been seen before
        if counter in first_occurrence:
            current_length = i - first_occurrence[counter]
            max_length = max(max_length, current_length)

        # Store first index of current count if not already stored
        else:
            first_occurrence[counter] = i

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input string of length n once. Inside the loop, dictionary operations (get and set) are performed which take O(1) time on average. Therefore, the time complexity is dominated by the single pass through the string, resulting in a linear time complexity with respect to the length of the input string.

Space Complexity

O(N) – The algorithm uses a dictionary (or similar data structure) to store the first occurrence of each counter value encountered while traversing the binary string. In the worst case, each character in the string alternates between '0' and '1', causing the counter value to change at each position. This would result in storing N different counter values and their corresponding indices in the dictionary, where N is the length of the input string. Therefore, the auxiliary space used by the algorithm is proportional to N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty string input	Return 0 immediately as an empty string has no balanced substring.
String with only one character	Return 0 since a single character cannot form a balanced substring.
String with all '0's	Return 0 as there are no '1's to balance the '0's.
String with all '1's	Return 0 as there are no '0's to balance the '1's.
String with alternating '0's and '1's (e.g., '010101')	The longest balanced substring will be the entire string if the counts are equal or twice the minimum count.
String with highly skewed distribution (e.g., many '0's followed by a few '1's)	The solution should correctly identify the longest balanced substring regardless of the distribution.
Very long string (potential performance bottleneck)	Ensure the algorithm has a time complexity of O(n) or O(n log n) to handle large inputs efficiently; avoid quadratic time complexity.
String with leading or trailing unbalanced characters	The algorithm should correctly identify the longest balanced substring within the string, ignoring any leading or trailing unbalanced characters.

Empty string input

How to Handle:

Return 0 immediately as an empty string has no balanced substring.

String with only one character

How to Handle:

Return 0 since a single character cannot form a balanced substring.

String with all '0's

How to Handle:

Return 0 as there are no '1's to balance the '0's.

String with all '1's

How to Handle:

Return 0 as there are no '0's to balance the '1's.

String with alternating '0's and '1's (e.g., '010101')

How to Handle:

The longest balanced substring will be the entire string if the counts are equal or twice the minimum count.

String with highly skewed distribution (e.g., many '0's followed by a few '1's)

How to Handle:

The solution should correctly identify the longest balanced substring regardless of the distribution.

Very long string (potential performance bottleneck)

How to Handle:

Ensure the algorithm has a time complexity of O(n) or O(n log n) to handle large inputs efficiently; avoid quadratic time complexity.

String with leading or trailing unbalanced characters

How to Handle:

The algorithm should correctly identify the longest balanced substring within the string, ignoring any leading or trailing unbalanced characters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the binary string?
What should I return if the input string is empty or null?
By 'balanced', do you mean the substring must contain an equal number of '0's and '1's?
If there are multiple balanced substrings of the same maximum length, should I return any one of them, or is there a specific criteria to choose one?
Can the input string contain characters other than '0' and '1'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first character of the string.
Then, consider the first two characters, then the first three, and so on, all the way to the end of the string.
For each of these 'substrings' (parts of the string), check if the number of zeros is equal to the number of ones.
If the number of zeros and ones are equal, remember the length of this substring.
Now, move to the second character of the string, and repeat the same process: look at the substring starting at the second character with length one, then two, then three, and so on.
Keep doing this, moving the starting point of the substring one character at a time, until you reach the end of the string.
As you check each substring, always remember the length of the longest balanced substring you've found so far.
After checking every possible substring, the longest balanced substring you remembered is your answer.

Code Implementation

def find_longest_balanced_substring_brute_force(binary_string):
    longest_balanced_substring_length = 0

    string_length = len(binary_string)

    for start_index in range(string_length):
        for end_index in range(start_index, string_length):
            substring = binary_string[start_index:end_index + 1]
            substring_length = len(substring)

            zeros_count = 0
            ones_count = 0

            for char in substring:
                if char == '0':
                    zeros_count += 1
                else:
                    ones_count += 1

            # Check if the current substring is balanced.
            if zeros_count == ones_count:

                # Update max length if current substring is longer
                if substring_length > longest_balanced_substring_length:
                    longest_balanced_substring_length = substring_length

    return longest_balanced_substring_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each '0' we see adds +1 to a counter and each '1' subtracts -1 from the counter.
As we go through the string, keep track of the first time each counter value appears. We can use a dictionary or similar tool for this.
If we encounter a counter value we've seen before, it means the section of the string between those two occurrences has an equal number of zeros and ones (it's balanced!).
Calculate the length of this balanced substring.
Keep updating the longest balanced substring found so far as we move through the string.
If the counter is zero, that means all the characters seen so far are balanced, and it could be the longest such substring.

Code Implementation

def find_longest_balanced_substring(binary_string):
    counter = 0
    first_occurrence = {0: -1}
    max_length = 0

    for i, bit in enumerate(binary_string):
        if bit == '0':
            counter += 1
        else:
            counter -= 1

        # Check if this counter value has been seen before
        if counter in first_occurrence:
            current_length = i - first_occurrence[counter]
            max_length = max(max_length, current_length)

        # Store first index of current count if not already stored
        else:
            first_occurrence[counter] = i

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return 0 immediately as an empty string has no balanced substring.
String with only one character	Return 0 since a single character cannot form a balanced substring.
String with all '0's	Return 0 as there are no '1's to balance the '0's.
String with all '1's	Return 0 as there are no '0's to balance the '1's.
String with alternating '0's and '1's (e.g., '010101')	The longest balanced substring will be the entire string if the counts are equal or twice the minimum count.
String with highly skewed distribution (e.g., many '0's followed by a few '1's)	The solution should correctly identify the longest balanced substring regardless of the distribution.
Very long string (potential performance bottleneck)	Ensure the algorithm has a time complexity of O(n) or O(n log n) to handle large inputs efficiently; avoid quadratic time complexity.
String with leading or trailing unbalanced characters	The algorithm should correctly identify the longest balanced substring within the string, ignoring any leading or trailing unbalanced characters.

Empty string input

How to Handle:

Return 0 immediately as an empty string has no balanced substring.

String with only one character

How to Handle:

Return 0 since a single character cannot form a balanced substring.

String with all '0's

How to Handle:

Return 0 as there are no '1's to balance the '0's.

String with all '1's

How to Handle:

Return 0 as there are no '0's to balance the '1's.

String with alternating '0's and '1's (e.g., '010101')

How to Handle:

The longest balanced substring will be the entire string if the counts are equal or twice the minimum count.

String with highly skewed distribution (e.g., many '0's followed by a few '1's)

How to Handle:

The solution should correctly identify the longest balanced substring regardless of the distribution.

Very long string (potential performance bottleneck)

How to Handle:

Ensure the algorithm has a time complexity of O(n) or O(n log n) to handle large inputs efficiently; avoid quadratic time complexity.

String with leading or trailing unbalanced characters

How to Handle:

The algorithm should correctly identify the longest balanced substring within the string, ignoring any leading or trailing unbalanced characters.