Find the Longest Balanced Substring of a Binary String solution and explanation
9 more videos on this problem
2609. Find the Longest Balanced Substring of a Binary String | Weekly Contest 339 | LeetCode 2609Bro Coders · 5:10 · 1K views
Leetcode 2609: Find the Longest Balanced Substring of a Binary StringAlgorithms Casts · 7:32 · 796 views
Leetcode Weekly contest 339 - Easy - Find the Longest Balanced Substring of a Binary StringPrakhar Agrawal · 6:35 · 571 views
2609. Find the Longest Balanced Substring of a Binary String (Leetcode Easy)Programming Live with Larry · 3:50 · 470 views
Leetcode Problem 2609: Find the Longest Balanced Substring of a Binary String | Weekly Contest 339OffCampus Phodenge | Aman Chowdhury · 9:19 · 353 views
2609.|| Find the Longest Balanced Substring of a Binary String || weekly contest 339Code Coder · 9:38 · 219 views
2609. Find the Longest Balanced Substring of a Binary String | weekly-contest-339 | LeetcodeCodeFod · 8:16 · 193 views
6362. Find the Longest Balanced Substring of a Binary String | Easy | Leetcode | Weekly Contest 339.Optimization · 1:53 · 139 views
2609. Find the Longest Balanced Substring of a Binary String | Weekly Contest 339 Leetcode SolutionCodeCake · 4:35 · 129 views
DAY 128/365 Find the Longest Balanced Substring of a Binary String(Leetcode 2609)CODE with TRIVENI · 3:59 · 123 views
The problem
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'
Approach overview
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 1: Count Balance Approach
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.
def longest_balanced_substring(s: str) -> int:
max_len = 0
balance = 0
last_zero = 0
for i, ch in enumerate(s):
balance += 1 if ch == '0' else -1
if balance == 0:
max_len = max(max_len, i - last_zero + 1)
if balance < 0:
balance = 0
last_zero = i + 1
return max_len
s = "01000111"
print(longest_balanced_substring(s))public class LongestBalancedSubstring {
public static int longestBalancedSubstring(String s) {
int maxLen = 0, balance = 0, lastZero = 0;
for (int i = 0; i < s.length(); i++) {
balance += (s.charAt(i) == '0') ? 1 : -1;
if (balance == 0) {
int currentLen = i - lastZero + 1;
if (currentLen > maxLen) maxLen = currentLen;
}
if (balance < 0) {
balance = 0;
lastZero = i + 1;
}
}
return maxLen;
}
public static void main(String[] args) {
String s = "01000111";
System.out.println(longestBalancedSubstring(s));
}
}#include <iostream>
#include <string>
using namespace std;
int longestBalancedSubstring(string s) {
int maxLen = 0, balance = 0, lastZero = 0;
for(size_t i = 0; i < s.size(); ++i) {
balance += (s[i] == '0') ? 1 : -1;
if(balance == 0) {
maxLen = max(maxLen, (int)(i - lastZero + 1));
}
if(balance < 0) {
balance = 0;
lastZero = i + 1;
}
}
return maxLen;
}
int main() {
string s = "01000111";
cout << longestBalancedSubstring(s);
return 0;
}function longestBalancedSubstring(s) {
let maxLen = 0, balance = 0, lastZero = 0;
for (let i = 0; i < s.length; i++) {
balance += (s[i] === '0') ? 1 : -1;
if (balance === 0) {
maxLen = Math.max(maxLen, i - lastZero + 1);
}
if (balance < 0) {
balance = 0;
lastZero = i + 1;
}
}
return maxLen;
}
let s = "01000111";
console.log(longestBalancedSubstring(s));#include <stdio.h>
#include <string.h>
int longestBalancedSubstring(char *s) {
int maxLen = 0, balance = 0, lastZero = 0;
for(int i = 0; s[i]; i++) {
balance += (s[i] == '0') ? 1 : -1;
if(balance == 0) {
int currentLen = i - lastZero + 1;
if(currentLen > maxLen) maxLen = currentLen;
}
if(balance < 0) {
balance = 0;
lastZero = i + 1;
}
}
return maxLen;
}
int main() {
char s[] = "01000111";
printf("%d", longestBalancedSubstring(s));
return 0;
}using System;
class Program {
static int LongestBalancedSubstring(string s) {
int maxLen = 0, balance = 0, lastZero = 0;
for (int i = 0; i < s.Length; i++) {
balance += (s[i] == '0') ? 1 : -1;
if (balance == 0) {
int currentLen = i - lastZero + 1;
if (currentLen > maxLen) maxLen = currentLen;
}
if (balance < 0) {
balance = 0;
lastZero = i + 1;
}
}
return maxLen;
}
static void Main() {
string s = "01000111";
Console.WriteLine(LongestBalancedSubstring(s));
}
}In Python, the code iterates over each character of the string, updating a balance value, and if the balance returns to zero, checks the length of the current balanced substring.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Prefix Sum Approach
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.
def longest_balanced_substring(s: str) -> int:
prefix_sum = {0: -1}
balance = 0
max_len = 0
for i, ch in enumerate(s):
balance += 1 if ch == '0' else -1
if balance in prefix_sum:
max_len = max(max_len, i - prefix_sum[balance])
else:
prefix_sum[balance] = i
return max_len
s = "01000111"
print(longest_balanced_substring(s))import java.util.HashMap;
public class LongestBalancedSubstring {
public static int longestBalancedSubstring(String s) {
HashMap<Integer, Integer> prefixSum = new HashMap<>();
int balance = 0, maxLen = 0;
prefixSum.put(0, -1);
for (int i = 0; i < s.length(); i++) {
balance += (s.charAt(i) == '0') ? 1 : -1;
if (prefixSum.containsKey(balance)) {
maxLen = Math.max(maxLen, i - prefixSum.get(balance));
} else {
prefixSum.put(balance, i);
}
}
return maxLen;
}
public static void main(String[] args) {
String s = "01000111";
System.out.println(longestBalancedSubstring(s));
}
}#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int longestBalancedSubstring(string s) {
unordered_map<int, int> prefixSum;
int balance = 0, maxLen = 0;
prefixSum[0] = -1;
for (size_t i = 0; i < s.size(); ++i) {
balance += (s[i] == '0') ? 1 : -1;
if (prefixSum.count(balance)) {
maxLen = max(maxLen, (int) i - prefixSum[balance]);
} else {
prefixSum[balance] = i;
}
}
return maxLen;
}
int main() {
string s = "01000111";
cout << longestBalancedSubstring(s);
return 0;
}function longestBalancedSubstring(s) {
const prefixSum = {0: -1};
let balance = 0, maxLen = 0;
for (let i = 0; i < s.length; i++) {
balance += (s[i] === '0') ? 1 : -1;
if (balance in prefixSum) {
maxLen = Math.max(maxLen, i - prefixSum[balance]);
} else {
prefixSum[balance] = i;
}
}
return maxLen;
}
let s = "01000111";
console.log(longestBalancedSubstring(s));#include <stdio.h>
#include <string.h>
int longestBalancedSubstring(char *s) {
int prefixSum[51] = {0};
int maxLen = 0, balance = 0, n = strlen(s);
for (int i = 0; i < n; i++) {
balance += (s[i] == '0') ? 1 : -1;
if (balance == 0) {
maxLen = i + 1;
}
if (prefixSum[balance + 25] != 0) {
int length = i - prefixSum[balance + 25] + 1;
if (length > maxLen) maxLen = length;
} else {
prefixSum[balance + 25] = i + 1;
}
}
return maxLen;
}
int main() {
char s[] = "01000111";
printf("%d", longestBalancedSubstring(s));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int LongestBalancedSubstring(string s) {
var prefixSum = new Dictionary<int, int> {{0, -1}};
int balance = 0, maxLen = 0;
for (int i = 0; i < s.Length; i++) {
balance += (s[i] == '0') ? 1 : -1;
if (prefixSum.TryGetValue(balance, out int index)) {
maxLen = Math.Max(maxLen, i - index);
} else {
prefixSum[balance] = i;
}
}
return maxLen;
}
static void Main() {
string s = "01000111";
Console.WriteLine(LongestBalancedSubstring(s));
}
}The Python solution makes use of a dictionary to maintain prefix sums, enabling swift detection of balanced substring endpoints based on balance values.
Time Complexity: O(n)
Space Complexity: O(n), due to the dictionary
Approach 3: Brute force
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.
function findTheLongestBalancedSubstring(s: string): number {
const n = s.length;
let ans = 0;
const check = (i: number, j: number): boolean => {
let cnt = 0;
for (let k = i; k <= j; ++k) {
if (s[k] === '1') {
++cnt;
} else if (cnt > 0) {
return false;
}
}
return cnt * 2 === j - i + 1;
};
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; j += 2) {
if (check(i, j)) {
ans = Math.max(ans, j - i + 1);
}
}
}
return ans;
}func findTheLongestBalancedSubstring(s string) (ans int) {
n := len(s)
check := func(i, j int) bool {
cnt := 0
for k := i; k <= j; k++ {
if s[k] == '1' {
cnt++
} else if cnt > 0 {
return false
}
}
return cnt*2 == j-i+1
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if check(i, j) {
ans = max(ans, j-i+1)
}
}
}
return
}impl Solution {
pub fn find_the_longest_balanced_substring(s: String) -> i32 {
let check = |i: usize, j: usize| -> bool {
let mut cnt = 0;
for k in i..=j {
if s.as_bytes()[k] == b'1' {
cnt += 1;
} else if cnt > 0 {
return false;
}
}
cnt * 2 == j - i + 1
};
let mut ans = 0;
let n = s.len();
for i in 0..n - 1 {
for j in (i + 1..n).rev() {
if j - i + 1 < ans {
break;
}
if check(i, j) {
ans = std::cmp::max(ans, j - i + 1);
break;
}
}
}
ans as i32
}
}Approach 4: Enumeration optimization
We use variables zero and one to record the number of continuous 0 and 1.
Traverse the string s, for the current character c:
- If the current character is
'0', we check ifoneis greater than0, if so, we resetzeroandoneto0, and then add1tozero. - If the current character is
'1', we add1toone, and update the answer toans = 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.
function findTheLongestBalancedSubstring(s: string): number {
let zero = 0;
let one = 0;
let ans = 0;
for (const c of s) {
if (c === '0') {
if (one > 0) {
zero = 0;
one = 0;
}
++zero;
} else {
ans = Math.max(ans, 2 * Math.min(zero, ++one));
}
}
return ans;
}func findTheLongestBalancedSubstring(s string) (ans int) {
zero, one := 0, 0
for _, c := range s {
if c == '0' {
if one > 0 {
zero, one = 0, 0
}
zero++
} else {
one++
ans = max(ans, 2*min(zero, one))
}
}
return
}impl Solution {
pub fn find_the_longest_balanced_substring(s: String) -> i32 {
let mut zero = 0;
let mut one = 0;
let mut ans = 0;
for &c in s.as_bytes().iter() {
if c == b'0' {
if one > 0 {
zero = 0;
one = 0;
}
zero += 1;
} else {
one += 1;
ans = std::cmp::max(ans, std::cmp::min(zero, one) * 2);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Count Balance Approach | Time Complexity: O(n) |
| Prefix Sum Approach | Time Complexity: O(n) |
| Brute force | – |
| Enumeration optimization | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find the Longest Balanced Substring of a Binary String easy or hard?
LeetCode classifies this problem as Easy. The main challenge is recognizing that valid substrings must follow the strict pattern of consecutive 0s followed by the same number of 1s. Once that constraint is clear, a simple linear scan solves the problem efficiently.
Find the Longest Balanced Substring of a Binary String Python/Java solution
Python and Java solutions typically implement the count-balance technique. Iterate through the string, track consecutive 0 and 1 counts, and update the maximum with 2 * min(count0, count1). The algorithm runs in O(n) time and requires only constant extra space.
How to solve Find the Longest Balanced Substring of a Binary String in O(n)?
Iterate through the string and count consecutive 0s first. When 1s begin, count them as well and compute the candidate length as 2 * min(count0, count1). Update the maximum length while scanning. Reset counters when a new 0 sequence begins. This single-pass technique guarantees O(n) time complexity.
What is the best approach for Find the Longest Balanced Substring of a Binary String?
The best approach is the Count Balance method, which scans the string and counts consecutive groups of 0s and 1s. For each 0-block followed by a 1-block, compute 2 * min(count0, count1) and track the maximum length. This solution runs in O(n) time with O(1) space and directly matches the problem’s 0^k1^k structure.
Is Find the Longest Balanced Substring of a Binary String asked at Google/Amazon/Meta?
Balanced substring and binary pattern problems frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. Variations often test string scanning, prefix sums, or two-pointer reasoning, making this problem a common practice question for entry-level coding interviews.
What data structure is used in Find the Longest Balanced Substring of a Binary String?
The optimal solution uses simple integer counters while scanning the string, so no additional data structures are required. Alternative implementations may use a hash map to store prefix sums when applying a prefix-sum-based strategy.
What is the time complexity of Find the Longest Balanced Substring of a Binary String?
The optimal solution runs in O(n) time because the binary string is scanned once while maintaining counts of consecutive characters. Space complexity can be O(1) using the count-balance approach or O(n) if a prefix sum map is used to store intermediate states.