# Find the Longest Balanced Substring of a Binary String
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-longest-balanced-substring-of-a-binary-string)
Canonical: https://scaleengineer.com/dsa/problems/find-the-longest-balanced-substring-of-a-binary-string
**Data structures:** String
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff)
---
## 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'`

# Approaches
## Brute Force: Check All Substrings
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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Expand From Center
A more optimized approach is to realize that any valid balanced substring must contain a `"01"` pattern at its core. We can iterate through the string to find every occurrence of this `"01"` pattern and then expand outwards from this 'center' to find the longest possible balanced substring.
**Time:** O(n^2), where n is the length of the string. The main loop runs `n` times. In the worst-case scenario (like a string of all '0's followed by all '1's), the inner expansion loops can scan a large portion of the string for each potential center, leading to quadratic complexity. · **Space:** O(1), as it only uses a constant number of variables for pointers and counters.
**Pros:** Significantly more efficient than the O(n^3) brute-force approach.; Reduces unnecessary checks by focusing only on promising candidates.
**Cons:** Not the most optimal solution.; It re-scans parts of the string multiple times during the expansion phase for different centers.
### Explanation
Instead of checking every substring, we can focus on the essential structure of a balanced substring: a block of zeroes followed immediately by a block of ones. This structure implies there must be a `"01"` transition point.

We can iterate through the string and look for every index `i` where `s.charAt(i) == '0'` and `s.charAt(i+1) == '1'`. Each such pair is a potential center of a balanced substring.

Once we find such a center at `(i, i+1)`, we use two pointers to expand outwards. A left pointer `l` starts at `i` and moves left, counting consecutive '0's. A right pointer `r` starts at `i+1` and moves right, counting consecutive '1's. After both pointers stop, we have a count of zeroes and ones. The length of the balanced substring we can form is twice the minimum of these two counts. We update a global `maxLength` with this value if it's larger than the current maximum.

```java
class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int maxLength = 0;
        int n = s.length();
        for (int i = 0; i < n - 1; i++) {
            // Find the "01" center
            if (s.charAt(i) == '0' && s.charAt(i + 1) == '1') {
                int zeros = 0;
                int ones = 0;
                
                // Expand left for '0's from i
                int l = i;
                while (l >= 0 && s.charAt(l) == '0') {
                    zeros++;
                    l--;
                }
                
                // Expand right for '1's from i+1
                int r = i + 1;
                while (r < n && s.charAt(r) == '1') {
                    ones++;
                    r++;
                }
                
                maxLength = Math.max(maxLength, 2 * Math.min(zeros, ones));
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength` to 0.
- Iterate through the string `s` with an index `i` from `0` to `n-2`.
- At each `i`, check if `s[i]` is '0' and `s[i+1]` is '1'. This `"01"` pair is a potential center of a balanced substring.
- If a center is found, use two pointers, `l = i` and `r = i + 1`.
- Expand the left pointer `l` towards the beginning of the string as long as the characters are '0's, counting them.
- Expand the right pointer `r` towards the end of the string as long as the characters are '1's, counting them.
- Calculate the number of consecutive zeroes (`zeros`) to the left and ones (`ones`) to the right.
- The length of the balanced substring for this center is `2 * min(zeros, ones)`.
- Update `maxLength = max(maxLength, 2 * min(zeros, ones))`.
- Return `maxLength` after the loop finishes.

## Single Pass Linear Scan
The most efficient solution involves a single pass through the string. By maintaining counts of the current consecutive block of zeroes and the subsequent consecutive block of ones, we can calculate the length of the longest balanced substring in linear time.
**Time:** O(n), where n is the length of the string. This is because we iterate through the string exactly once. · **Space:** O(1), as we only use a few constant-space variables to store the counts and the maximum length.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Highly efficient and scalable.
**Cons:** The logic for resetting the counters can be slightly less intuitive to grasp initially compared to more direct methods.
### Explanation
This approach optimizes the process down to a single scan. We use two counters, `zeros` and `ones`, to keep track of the lengths of the current consecutive blocks of '0's and '1's. 

We iterate through the string. When we see a '0', we increment the `zeros` counter. However, if the '0' follows a block of '1's (i.e., `ones > 0`), it means the previous `0...1...` group has ended. We must reset our counts (`zeros = 1`, `ones = 0`) to start counting a new potential group. When we see a '1', we simply increment the `ones` counter.

At every step, after updating the counters, we have a potential balanced substring formed by the preceding `zeros` and the current `ones`. The length of this substring is `2 * min(zeros, ones)`. We continuously update a `maxLength` variable with the maximum length found so far. This way, we find the result by examining each character only once.

```java
class Solution {
    public int findTheLongestBalancedSubstring(String s) {
        int maxLength = 0;
        int zeros = 0;
        int ones = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                // If we encounter a '0' after a sequence of '1's, 
                // the previous group is finished. Start a new one.
                if (ones > 0) {
                    zeros = 0;
                    ones = 0;
                }
                zeros++;
            } else { // s.charAt(i) == '1'
                ones++;
            }
            
            // A balanced substring can be formed with the current number of ones
            // and the preceding number of zeros.
            maxLength = Math.max(maxLength, 2 * Math.min(zeros, ones));
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`, `zeros = 0`, and `ones = 0`.
- Iterate through the string `s` character by character from left to right.
- If the current character is '0':
  - Check if the previous character was a '1' (which we can infer if `ones > 0`). If so, it means a `...10...` pattern has occurred, breaking the current `0...1...` group. Reset `zeros` and `ones` to 0 to start a new group.
  - Increment `zeros`.
- If the current character is '1':
  - Increment `ones`.
- After processing each character, we have the count of the current consecutive '1's block (`ones`) and the '0's block that came immediately before it (`zeros`).
- Calculate a potential balanced substring length as `2 * min(zeros, ones)`.
- Update `maxLength = max(maxLength, 2 * min(zeros, ones))`.
- After the loop, return `maxLength`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findTheLongestBalancedSubstring(string s) {
    int n = s.size();
    int ans = 0;
    auto check = [&](int i, int j) -> bool {
      int cnt = 0;
      for (int k = i; k <= j; ++k) {
        if (s[k] == '1') {
          ++cnt;
        } else if (cnt) {
          return false;
        }
      }
      return cnt * 2 == j - i + 1;
    };
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (check(i, j)) {
          ans = max(ans, j - i + 1);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def findTheLongestBalancedSubstring ( self , s : str ) -> int : def check ( i , j ): cnt = 0 for k in range ( i , j + 1 ): if s [ k ] == '1' : cnt += 1 elif cnt : return False return cnt * 2 == ( j - i + 1 ) n = len ( s ) ans = 0 for i in range ( n ): for j in range ( i + 1 , n ): if check ( i , j ): ans = max ( ans , j - i + 1 ) return ans
```