最长平衡子字符串
难度:
标签:
题目描述
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'
代码结果
运行时间: 30 ms, 内存: 16.1 MB
/*
思路：
1. 使用Stream和lambda表达式来优化子字符串的检查过程。
2. 通过将原字符串的所有可能子字符串生成流，并在流中检查平衡子字符串的最大长度。
*/
import java.util.stream.IntStream;
public class BalancedSubstringStream {
public static int findLongestBalancedSubstring(String s) {
return IntStream.range(0, s.length())
.flatMap(i -> IntStream.range(i + 1, s.length() + 1)
.map(j -> s.substring(i, j)))
.filter(BalancedSubstringStream::isBalanced)
.mapToInt(String::length)
.max()
.orElse(0);
}
private static boolean isBalanced(String substring) {
long count0 = substring.chars().filter(c -> c == '0').count();
long count1 = substring.chars().filter(c -> c == '1').count();
if (count0 != count1) return false;
boolean seenOne = false;
for (char c : substring.toCharArray()) {
if (c == '1') seenOne = true;
if (c == '0' && seenOne) return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "01000111";
String s2 = "00111";
String s3 = "111";
System.out.println(findLongestBalancedSubstring(s1)); // 6
System.out.println(findLongestBalancedSubstring(s2)); // 4
System.out.println(findLongestBalancedSubstring(s3)); // 0
}
}
解释
方法:
这个题解的思路主要是基于追踪遇到的0和1的数量。初始设定一个标记flag为True表示当前正在统计0的数量。当遇到0且flag为True时，增加0的数量。若遇到1且已有0存在，将flag设置为False表示开始匹配1和之前的0。每成功匹配一对0和1时，减少0的计数并增加已匹配对的计数。若遇到0且flag为False，表示当前0不可能与前面的1匹配，因此重新设置flag为True并重置0的计数与匹配对的计数。通过维护一个最大值ans来记录至今发现的最长平衡子字符串长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，当遇到'1'且已有0存在时，你是如何确定此时应该开始匹配1和之前0而不是继续计数0的？
▷🦆
题解中提到，如果遇到0且flag为False时，会重置0的数量并重新计数，这种情况下之前统计的0和1的匹配对会如何处理？是否可能会遗漏一些有效的匹配对？
▷🦆
题解中使用的方法似乎只在遇到1时更新最长平衡子字符串的长度，为什么没有在遇到0时也更新？是否有可能在某些情况下遗漏更新最大长度？
▷