Find the Longest Balanced Substring of a Binary String

Find the Longest Balanced Substring of a Binary String - Problem

String Easy

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
The number of zeroes is equal to the number of ones

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.

Input & Output

Example 1 — Basic Pattern

$ Input: s = "01000111"

› Output: 6

💡 Note: The longest balanced substring is "000111" with 3 zeros followed by 3 ones, giving length 6

Example 2 — Multiple Patterns

$ Input: s = "00111"

› Output: 4

💡 Note: We have 2 zeros and 3 ones in pattern. The longest balanced part is "0011" with length 4

Example 3 — No Valid Pattern

$ Input: s = "111"

› Output: 0

💡 Note: No zeros present, so no balanced substring is possible

Constraints

1 ≤ s.length ≤ 50
s consists only of '0' and '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with mixed 0s and 1s

Find Pattern

Locate substrings where zeros appear before ones

Output

Length of longest balanced substring

Key Takeaway

🎯 Key Insight: Look for consecutive patterns of zeros followed by ones, then take the minimum count times 2

Asked in

a Amazon 25 M Microsoft 18

The key insight is that a balanced substring must have the pattern '00...0011...11' with equal counts. Best approach is the optimized single-pass solution that identifies consecutive zero-one patterns. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimization	O(n)	O(1)	Track consecutive patterns of zeros followed by ones
Brute Force - Check All Substrings	O(n³)	O(1)	Check every possible substring to see if it's balanced

Single Pass Optimization — Algorithm Steps

Step 1: Scan string and count consecutive zeros
Step 2: When we hit ones, count consecutive ones
Step 3: Calculate balanced length as 2 * min(zeros, ones)

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Pattern

Identify consecutive zeros followed by consecutive ones

Count Elements

Count zeros and ones in the pattern

Calculate Length

Balanced length = 2 × min(zeros, ones)

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(char* s) {
    int n = strlen(s);
    int maxLength = 0;
    int i = 0;
    
    while (i < n) {
        // Count consecutive zeros
        int zeros = 0;
        while (i < n && s[i] == '0') {
            zeros++;
            i++;
        }
        
        // Count consecutive ones
        int ones = 0;
        while (i < n && s[i] == '1') {
            ones++;
            i++;
        }
        
        // Calculate balanced length from this pattern
        if (zeros > 0 && ones > 0) {
            int balancedLength = 2 * min(zeros, ones);
            maxLength = max(maxLength, balancedLength);
        }
    }
    
    return maxLength;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track counts

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler