替换子串得到平衡字符串
难度:
标签:
题目描述
代码结果
运行时间: 94 ms, 内存: 16.4 MB
/*
* 思路:
* 1. 统计每个字符的出现次数。
* 2. 计算每个字符超过n/4的部分,这些部分需要通过替换来平衡。
* 3. 使用滑动窗口技术找到最小的子串,使得替换这个子串后字符串平衡。
*/
import java.util.stream.IntStream;
public class BalancedStringStream {
public int balancedString(String s) {
int n = s.length();
int k = n / 4;
int[] count = new int[128];
s.chars().forEach(c -> count[c]++);
int[] minLen = { n };
IntStream.range(0, n).forEach(i -> {
count[s.charAt(i)]--;
while (count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
minLen[0] = Math.min(minLen[0], i - j + 1);
count[s.charAt(j++)]++;
}
});
return minLen[0];
}
}
解释
方法:
本题解使用滑动窗口(sliding window)策略来找到使字符串平衡的最小子串长度。首先,计算每个字符'Q', 'W', 'E', 'R'的出现次数,并确定每个字符应有的平均出现次数(n/4)。接着,创建一个字典d来记录每个字符超出平均值的数量。若所有字符的数量都不超过平均值,则字符串已经平衡,直接返回0。使用双指针技术(左指针l和右指针r),扩展右指针以包含足够的超额字符,然后逐步移动左指针以缩小窗口,直到窗口内的字符不再能覆盖所有超额字符。过程中记录并更新最小窗口长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在初始化字典d时,只记录了超过平均值的字符,而没有记录低于平均值的字符的信息?
▷🦆
在滑动窗口中,当匹配到所有超额字符并尝试缩小窗口时,如果s[l]不在字典d中,是否应该移动左指针l,这样的操作对结果计算有何影响?
▷🦆
解题思路中提到使用双指针策略,但实际操作似乎更接近于滑动窗口方法。请问双指针和滑动窗口在概念上有何不同?
▷