[LeetCode] 2609. Find the Longest Balanced Substring of a Binary String

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’

最长平衡子字符串。

给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。

思路

这里我提供一个双指针的做法。对于每个 index (i, i + 1)，我们把位置 i 上的字母当做 0，把位置 i + 1 上的字母当做 1，看看往左往右能同时延伸多长。这个思路借鉴了从中间往两边找最长回文子串的思路。

复杂度

时间O(n^2) - worst case
空间O(1)

代码

Java实现

class Solution {
    int res = 0;

    public int findTheLongestBalancedSubstring(String s) {
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '0') {
                helper(s, i, i + 1, '0', '1');
            }
        }
        return res;
    }

    private void helper(String s, int left, int right, char charLeft, char charRight) {
        while (left >= 0 && right < s.length() && s.charAt(left) == charLeft && s.charAt(right) == charRight) {
            left--;
            right++;
        }
        res = Math.max(res, right - left - 1);
    }
}