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'Problem Overview: Given a binary string s, return the length of the longest balanced substring. A substring is balanced when it contains consecutive 0s followed immediately by the same number of 1s (pattern 0^k1^k). The goal is to find the maximum possible length 2 * k among all such substrings.
Approach 1: Count Balance Approach (O(n) time, O(1) space)
Scan the string while counting consecutive groups of 0s and 1s. For every block of 0s followed by a block of 1s, the balanced substring length equals 2 * min(count0, count1). Keep track of the maximum value seen. The key insight: a valid substring must contain only one transition from 0 to 1, and its length depends on the smaller group. This approach processes the string once, updating counts as you iterate, which makes it the most practical solution for interviews and production code. Since only a few counters are stored, the space usage stays constant. This technique relies heavily on sequential traversal patterns common in string problems.
Approach 2: Prefix Sum Approach (O(n) time, O(n) space)
Treat 0 as -1 and 1 as +1, then compute a running prefix sum while iterating through the string. Equal numbers of 0s and 1s produce the same cumulative balance difference. By storing the earliest occurrence of each prefix value in a hash map, you can determine candidate balanced segments. However, because the substring must follow the strict 0...01...1 order, additional checks ensure the segment does not contain alternating patterns. This method is useful when practicing prefix sum techniques or when adapting similar logic for more complex substring problems. It requires extra memory for storing prefix indices but still runs in linear time.
Recommended for interviews: The Count Balance Approach is what interviewers usually expect. It demonstrates strong understanding of pattern constraints in a string scan and achieves optimal O(n) time with O(1) space. The prefix sum version is valuable as a conceptual alternative and helps build intuition for balance-based substring problems.
The idea is to traverse the string while maintaining a balance counter. Increase the counter when the character is 0 and decrease it when it is 1. Track the maximum length when the balance is zero, indicating a balanced substring.
In this C solution, we iterate over the string adjusting a balance counter based on the characters, and determine the length of the current balanced substring whenever the balance is zero.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as only a fixed amount of additional space is used.
This approach involves using a prefix sum array to store the cumulative count of zeroes minus ones at each position. When the same value appears twice, a balanced substring is implied between those positions.
In this C solution, prefix sums are maintained to detect duplicate balances that indicate balanced substrings between them.
Time Complexity: O(n)
Space Complexity: O(n), due to the prefix sum array
Since the range of n is small, we can enumerate all substrings s[i..j] to check if it is a balanced string. If so, update the answer.
The time complexity is O(n^3), and the space complexity is O(1). Where n is the length of string s.
We use variables zero and one to record the number of continuous 0 and 1.
Traverse the string s, for the current character c:
'0', we check if one is greater than 0, if so, we reset zero and one to 0, and then add 1 to zero.'1', we add 1 to one, and update the answer to ans = max(ans, 2 times min(one, zero)).After the traversal is complete, we can get the length of the longest balanced substring.
The time complexity is O(n), and the space complexity is O(1). Where n is the length of string s.
| Approach | Complexity |
|---|---|
| Count Balance Approach | Time Complexity: O(n), where n is the length of the string. |
| Prefix Sum Approach | Time Complexity: O(n) |
| Brute force | — |
| Enumeration optimization | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Balance Approach | O(n) | O(1) | Best general solution when scanning a binary string for 0→1 grouped patterns |
| Prefix Sum Approach | O(n) | O(n) | Useful when practicing prefix sum or adapting to more flexible balance substring variants |
2609. Find the Longest Balanced Substring of a Binary String | Weekly Contest 339 | LeetCode 2609 • Bro Coders • 1,263 views views
Watch 9 more video solutions →Practice Find the Longest Balanced Substring of a Binary String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor