平衡子串计数器是Java实习面试中高频出现的字符串相关算法题，核心目标是统计给定字符串中所有符合平衡规则的子串数量。这里的平衡通常指子串中两种指定字符的出现次数相等，比如常见的场景是统计字符串中0和1数量相等的子串总数。
平衡子串的核心定义
首先要明确平衡子串的判定标准，不同题目可能会指定不同的平衡规则，最常见的两种规则如下：
- 针对仅包含0和1的字符串，平衡子串要求子串中0的个数和1的个数完全相等
- 针对包含多种字符的字符串，可能要求某两种指定字符的出现次数相等，其他字符不纳入计数范围
需要注意的是，子串是连续的字符序列，和子序列的概念不同，这一点是解题的基础前提。
实现思路拆解
暴力解法思路
最直观的思路是枚举所有可能的子串，逐个判断是否符合平衡规则。枚举所有子串需要两层循环，判断每个子串的字符计数需要一层循环，整体时间复杂度为O(n³)，当字符串长度较大时效率极低，不适合实际应用。
前缀和优化思路
我们可以用前缀和的思路来降低时间复杂度。以0和1平衡的场景为例，我们把0视为-1，1视为1，计算字符串的前缀和。如果两个位置的前缀和相等，说明这两个位置之间的子串中0和1的数量相等，也就是平衡子串。
具体逻辑为：初始化一个哈希表，记录每个前缀和出现的次数，初始时前缀和为0的次数为1。遍历字符串时实时更新当前前缀和，查看哈希表中该前缀和已经出现的次数，次数就是新增的平衡子串数量，同时把当前前缀和的出现次数加1。
完整Java实现代码
以下是针对0和1平衡场景的完整实现代码：
import java.util.HashMap;
import java.util.Map;
public class BalancedSubstringCounter {
public static int countBalancedSubstrings(String s) {
// 哈希表存储前缀和出现的次数，key是前缀和，value是出现次数
Map<Integer, Integer> prefixCount = new HashMap<>();
// 初始前缀和为0的情况出现1次，对应从字符串开头开始的平衡子串
prefixCount.put(0, 1);
int currentSum = 0;
int result = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 0转为-1，1转为1，更新当前前缀和
if (c == '0') {
currentSum -= 1;
} else if (c == '1') {
currentSum += 1;
}
// 如果当前前缀和已经出现过，说明之前的位置到当前位置之间的子串是平衡的
if (prefixCount.containsKey(currentSum)) {
result += prefixCount.get(currentSum);
}
// 更新当前前缀和的出现次数
prefixCount.put(currentSum, prefixCount.getOrDefault(currentSum, 0) + 1);
}
return result;
}
public static void main(String[] args) {
// 测试用例1：包含多个平衡子串
String test1 = "0011";
System.out.println("测试字符串" + test1 + "的平衡子串数量：" + countBalancedSubstrings(test1));
// 测试用例2：无平衡子串
String test2 = "000";
System.out.println("测试字符串" + test2 + "的平衡子串数量：" + countBalancedSubstrings(test2));
// 测试用例3：混合场景
String test3 = "0101";
System.out.println("测试字符串" + test3 + "的平衡子串数量：" + countBalancedSubstrings(test3));
}
}
常见误区说明
- 不要混淆子串和子序列的概念，平衡子串要求字符连续，不能跳过中间的字符
- 初始化哈希表时要放入前缀和0的次数为1，否则会漏掉从字符串第一个字符开始的平衡子串
- 如果题目指定的平衡字符不是0和1，只需要调整字符转数值的逻辑即可，前缀和的核心思路不变
这类题目考察的核心是前缀和的灵活运用，掌握思路后可以快速适配不同的平衡规则变种，是实习面试中需要重点掌握的算法题类型。