Find the Longest Balanced Substring of a Binary String — LeetCode 2609 Python Solution

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.

Example

Input

s = "01000111"

Output

6

Explanation

The longest balanced substring is "000111", which has length 6.

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2609. Find the Longest Balanced Substring of a Binary String is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems