Watch 10 video solutions for Find the Longest Balanced Substring of a Binary String, a easy level problem involving String. This walkthrough by Bro Coders has 1,263 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |