2609. Find the Longest Balanced Substring of a Binary String
Description
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'
Solutions
Solution 1: Brute force
Since the range of $n$ is small, we can enumerate all substrings $s[i..j]$ to check if it is a balanced string. If so, update the answer.
The time complexity is $O(n^3)$, and the space complexity is $O(1)$. Where $n$ is the length of string $s$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|