Find the Longest Balanced Substring of a Binary String - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

EasyString19 min readAsked at: Tinkoff

Practice this problem

Problem Statement

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.

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

In this C solution, prefix sums are maintained to detect duplicate balances that indicate balanced substrings between them.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n), due to the prefix sum array

Try this approach in the editor →

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

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 if one is greater than 0, if so, we reset zero and one to 0, and then add 1 to zero.
If the current character is '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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Count Balance Approach	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.
Prefix Sum Approach	Time Complexity: O(n) Space Complexity: O(n), due to the prefix sum array
Brute force	—
Enumeration optimization	—

Detailed 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

Video Solution

2609. Find the Longest Balanced Substring of a Binary String | Weekly Contest 339 | LeetCode 2609 • Bro Coders • 1,295 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Longest Balanced Substring of a Binary String with our built-in code editor and test cases.

Practice on FleetCode

Longest Substring Without Repeating Characters

Longest Palindromic Substring

Problem Info

DifficultyEasy

Acceptance46.6%

Approaches4

Reading time19 min

Asked at

Tinkoff

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Count Balance Approach

Code

Complexity

Approach 2: Prefix Sum Approach

Code

Complexity

Approach 3: Brute force

Code

Approach 4: Enumeration optimization

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents