1234. 替换子串得到平衡字符串
有一个只含有 'Q', 'W', 'E', 'R' 四种字符,且长度为 n 的字符串。
假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。
给你一个这样的字符串 s,请通过「替换一个子串」的方式,使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串,则返回 0。
示例 1:
输入:s = "QWER"
输出:0
解释:s 已经是平衡的了。
示例 2:
输入:s = "QQWE"
输出:1
解释:我们需要把一个 'Q' 替换成 'R',这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3:
输入:s = "QQQW"
输出:2
解释:我们可以把前面的 "QQ" 替换成 "ER"。
示例 4:
输入:s = "QQQQ"
输出:3
解释:我们可以替换后 3 个 'Q',使 s = "QWER"
解答:双指针+滑动窗口
class Solution {
public int balancedString(String s) {
int n=s.length();
int res=n;
int[] tol=new int[4];
//统计每个字符出现的次数
for(char c:s.toCharArray())tol[get(c)]++;
//本身就符合条件直接返回0
if(tol[0]==n/4&&tol[1]==n/4&&tol[2]==n/4)return 0;
//统计l-r区间每个字符出现的次数
int[] sum=new int[4];
//l左指针,r右指针
for(int r=0,l=0;r<n;r++){
sum[get(s.charAt(r))]++;
while(l<=r&&check(tol,sum,n/4)){
res=Math.min(r-l+1,res);
//缩短区间
sum[get(s.charAt(l++))]--;
}
}
return res;
}
int get(char c){
if(c=='Q')return 0;
if(c=='W')return 1;
if(c=='E')return 2;
return 3;
}
//通过check找最短待替换字串
boolean check(int[] tol,int[] sum,int target){
for(int i=0;i<4;i++){
//如果本身都大于n/4,不符合条件直接返回false
if(tol[i]-sum[i]>target)return false;
}
return true;
}
}