平衡子串计数问题的核心是指统计字符串中满足特定平衡条件的连续子串数量，最常见的平衡规则是子串中两种指定字符的出现次数相等，比如统计字符串中0和1数量相等的子串总数，或者统计大小写字母数量相等的子串总数。这类题目主要考察对字符串遍历逻辑的把控和计数技巧的运用。
平衡子串的定义与常见考察形式
首先需要明确题目中平衡子串的具体定义，不同题目可能会给出不同的平衡规则，常见的有以下几种：
- 子串中两种固定字符的出现次数相等，比如仅包含0和1的字符串中0和1数量相等的子串
- 子串中字符的种类和数量满足特定比例，比如元音字母和辅音字母数量相等的子串
- 子串的左右两部分满足对称计数条件，比如前半部分和后半部分相同字符数量相等
在Java实习题中，最基础也最常考的是第一种情况，即两种字符数量相等的子串计数，我们后续的实现也围绕这种场景展开。
基础实现思路：暴力遍历法
暴力遍历法的逻辑比较直观，就是枚举所有可能的子串，然后逐个判断子串是否满足平衡条件，最后统计符合条件的子串总数。这种方法的实现门槛低，适合初学者理解题目逻辑。
实现步骤
- 外层循环遍历子串的起始位置，从0到字符串长度减1
- 内层循环遍历子串的结束位置，从起始位置到字符串长度减1
- 对每个起始和结束位置对应的子串，统计两种目标字符的出现次数
- 如果两种字符次数相等，计数加1
代码示例
public class BalancedSubstringCounter {
// 统计字符串s中字符c1和c2数量相等的子串总数
public static int countBalancedSubstringsBruteForce(String s, char c1, char c2) {
int n = s.length();
int count = 0;
// 外层循环遍历子串起始位置
for (int i = 0; i < n; i++) {
// 内层循环遍历子串结束位置
for (int j = i; j < n; j++) {
int cnt1 = 0;
int cnt2 = 0;
// 统计当前子串中c1和c2的数量
for (int k = i; k <= j; k++) {
if (s.charAt(k) == c1) {
cnt1++;
} else if (s.charAt(k) == c2) {
cnt2++;
}
}
// 数量相等则计数加1
if (cnt1 == cnt2) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
String testStr = "110010";
char target1 = '1';
char target2 = '0';
int result = countBalancedSubstringsBruteForce(testStr, target1, target2);
System.out.println("平衡子串总数为：" + result);
}
}
这种暴力方法的时间复杂度是O(n³)，其中n是字符串的长度，当字符串长度较大时会有明显的性能问题，在实习面试中如果只给出这种解法，通常还需要优化方案。
优化实现思路：前缀和计数法
前缀和计数法的核心是将两种字符的数量差作为前缀和，利用哈希表记录不同前缀和出现的次数，从而将时间复杂度降到O(n)。
实现逻辑
我们可以定义一个变量diff，遍历字符串时，遇到c1就加1，遇到c2就减1，其他字符不影响。那么对于两个位置i和j，如果i位置的diff值和j位置的diff值相等，说明从i+1到j的子串中c1和c2的数量相等。我们只需要用哈希表记录每个diff值出现的次数，每次遇到相同的diff值，就把之前出现的次数加到结果中。
代码示例
import java.util.HashMap;
import java.util.Map;
public class BalancedSubstringCounter {
// 优化方法：前缀和计数法统计平衡子串
public static int countBalancedSubstringsOptimized(String s, char c1, char c2) {
int n = s.length();
int diff = 0;
int count = 0;
// 哈希表记录diff值出现的次数，初始时diff=0出现1次（对应空串的情况）
Map<Integer, Integer> diffCount = new HashMap<>();
diffCount.put(0, 1);
for (int i = 0; i < n; i++) {
char currentChar = s.charAt(i);
if (currentChar == c1) {
diff++;
} else if (currentChar == c2) {
diff--;
}
// 如果当前diff值之前出现过，说明存在对应数量的平衡子串
if (diffCount.containsKey(diff)) {
count += diffCount.get(diff);
}
// 更新当前diff值的出现次数
diffCount.put(diff, diffCount.getOrDefault(diff, 0) + 1);
}
return count;
}
public static void main(String[] args) {
String testStr = "110010";
char target1 = '1';
char target2 = '0';
int result = countBalancedSubstringsOptimized(testStr, target1, target2);
System.out.println("平衡子串总数为：" + result);
}
}
这种优化方法的时间复杂度是O(n)，空间复杂度是O(n)，适合处理长字符串的场景，也是实习面试中更受青睐的解法。
两种方案的对比
| 方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力遍历法 | O(n³) | O(1) | 字符串长度较短，逻辑验证场景 |
| 前缀和计数法 | O(n) | O(n) | 字符串长度较长，性能要求高的场景 |
边界情况处理
在实现平衡子串计数时，还需要注意以下边界情况：
- 字符串为空或者长度小于2时，不存在平衡子串，直接返回0
- 字符串中只包含一种目标字符时，不存在两种字符数量相等的子串，返回0
- 如果平衡规则涉及更多字符，需要调整diff的计算逻辑，比如三种字符的话可以用两个维度的diff来记录
掌握平衡子串计数的核心逻辑后，无论题目怎么调整平衡规则，都可以通过调整计数逻辑来快速实现正确的解法，这也是这类题目在Java实习考察中的核心价值。