替换子串得到平衡字符串【LC1234】
有一个只含有
'Q', 'W', 'E', 'R'四种字符，且长度为n的字符串。假如在该字符串中，这四个字符都恰好出现
n/4次，那么它就是一个「平衡字符串」。给你一个这样的字符串
s，请通过「替换一个子串」的方式，使原字符串s变成一个「平衡字符串」。你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回
0。
隐晦了点竟然就做不大出来了，哎还是不够不够数量
最近事情好多啊，还要准备上学期的期末考。。。
思路：当删除连续子字符串后，剩余每个字符的数量小于等于n / 4 时，可以替换该子串使s称为平衡子字符串，因此可以使用滑动窗口枚举每个子字符串的左端点，找到符合条件的右端点的最小位置，此时滑动串口的大小即为子串的长度，取最小值返回即可
实现
- 使用哈希表记录每个字符的数量
- 使用
check函数检验是否每个字符均小于n/4
class Solution { public int balancedString(String s) { Map<Character, Integer> map = new HashMap<>(); int n = s.length(), m = n / 4; int res = n; int r = 0; // 初始化哈希表 存储整个字符串中每个字符的个数 for (int i = 0; i < n; i++){ char c = s.charAt(i); map.put(c, map.getOrDefault(c, 0) + 1); } // 如果初始字符串即为平衡字符串 返回0 if (check(map, m)) return 0; // 枚举所有可以被替换的子串：枚举每个左端点，找到其最小的右端点值 for (int l = 0; l < n; l++){ // 如果有字符个数>m，那么移动右端点 while (r < n && !check(map, m)){ map.put(s.charAt(r), map.get(s.charAt(r)) - 1); r++; } // 如果找不到合法的右端点 退出循环 if (!check(map, m)) break; // 更新结果 res = Math.min(res, r - l); // 将左端点复原（下次循环 左端点不在替换子串中） map.put(s.charAt(l), map.get(s.charAt(l)) + 1); } return res; } // 检查每个字符的数量是否都小于等于m public boolean check(Map<Character, Integer> map, int m){ for (var node : map.entrySet()){ if (node.getValue() > m) return false; } return true; } }
复杂度
- 时间复杂度：O(n)
空间复杂度：O ( ∑ ) ，∑为字符集的大小，本题中为4
