Scale Engineer

Find the Longest Balanced Substring of a Binary String

Easy
#2389Time: O(n^3), where n is the length of the string. There are O(n^2) possible substrings. For each substring, the `isBalanced` check takes O(n) time in the worst case. Thus, the total time complexity is O(n^2 * n) = O(n^3).Space: O(n), where n is the length of the string. In Java, `s.substring()` can create a new string object, which in the worst case can have a length of n.1 company
Data structures
String
Companies
Tinkoff

Prompt

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'

Approaches

3 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every single substring of the given string s. For each substring, it validates whether it is 'balanced' according to the problem's definition: an equal number of zeroes and ones, with all zeroes appearing before all ones.

Algorithm

  • Initialize a variable maxLength to 0.
  • Generate all possible substrings of s using nested loops. The outer loop i iterates from 0 to n-1 (start index), and the inner loop j iterates from i to n-1 (end index).
  • For each substring, create a helper function isBalanced(sub) to check if it meets the criteria.
  • The isBalanced function checks if the substring's length is even (say, 2k), if its first k characters are all '0's, and if its last k characters are all '1's.
  • If a substring is balanced, update maxLength = max(maxLength, length of substring).
  • After checking all substrings, return maxLength.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. We can use two nested loops to generate every possible contiguous substring. The outer loop selects the starting index i, and the inner loop selects the ending index j.

For each substring obtained, we pass it to a helper function. This function first checks if the length is even, say 2k. If not, it can't be balanced. If it is even, it then verifies that the first half of the substring consists entirely of k zeroes and the second half consists entirely of k ones.

We maintain a variable, maxLength, initialized to 0. Whenever we find a balanced substring, we compare its length with maxLength and update it if the new length is greater. After iterating through all possible substrings, maxLength will hold the length of the longest one found.

class Solution {    public int findTheLongestBalancedSubstring(String s) {        int n = s.length();        int maxLength = 0;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                String sub = s.substring(i, j + 1);                if (isBalanced(sub)) {                    maxLength = Math.max(maxLength, sub.length());                }            }        }        return maxLength;    }     private boolean isBalanced(String sub) {        int len = sub.length();        if (len == 0 || len % 2 != 0) {            return false;        }        int k = len / 2;        // Check first half for '0's        for (int i = 0; i < k; i++) {            if (sub.charAt(i) != '0') {                return false;            }        }        // Check second half for '1's        for (int i = k; i < len; i++) {            if (sub.charAt(i) != '1') {                return false;            }        }        return true;    }}

Complexity

Time

O(n^3), where n is the length of the string. There are O(n^2) possible substrings. For each substring, the `isBalanced` check takes O(n) time in the worst case. Thus, the total time complexity is O(n^2 * n) = O(n^3).

Space

O(n), where n is the length of the string. In Java, `s.substring()` can create a new string object, which in the worst case can have a length of n.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Guaranteed to find the correct answer by checking all possibilities.

Cons

  • Highly inefficient due to its cubic time complexity.

  • Generates and checks many substrings that cannot possibly be balanced.

  • Likely to time out on larger constraints, though it will pass for this problem's constraints (n <= 50).

Solutions

class Solution {public  int findTheLongestBalancedSubstring(String s) {    int n = s.length();    int ans = 0;    for (int i = 0; i < n; ++i) {      for (int j = i + 1; j < n; ++j) {        if (check(s, i, j)) {          ans = Math.max(ans, j - i + 1);        }      }    }    return ans;  }private  boolean check(String s, int i, int j) {    int cnt = 0;    for (int k = i; k <= j; ++k) {      if (s.charAt(k) == '1') {        ++cnt;      } else if (cnt > 0) {        return false;      }    }    return cnt * 2 == j - i + 1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem