网站建设如何交税,在线图片编辑器马赛克,域名防红短链接生成,电脑浏览器打不开怎么回事题目链接 Leetcode.1234 替换子串得到平衡字符串 Rating #xff1a; 1878 题目描述
有一个只含有 Q, W, E, R四种字符#xff0c;且长度为 n 的字符串。
假如在该字符串中#xff0c;这四个字符都恰好出现 n/4次#xff0c;那么它就是一个「平衡字符串」。
给你一个这样…题目链接 Leetcode.1234 替换子串得到平衡字符串 Rating 1878 题目描述
有一个只含有 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”。 提示
1s.length1051 s.length 10^51s.length105s.length是 4的倍数s中只含有 Q, W, E, R四种字符
分析
s的长度为 n那么每一个 Q, W, E, R的个数都应该是 m n / 4。
用两个指针 i和j,维护一个 [i,j]的区间滑动窗口要替换的就是这个区间。除开这个区间的每一个字符的出现次数都 小于等于m的话这个区间就可以替换。否则不可以。
时间复杂度O(n)O(n)O(n)
代码
class Solution {
public:int balancedString(string s) {int n s.size();unordered_mapchar,int cnt;//先记录每个字符的出现次数for(auto c:s) cnt[c];int m n / 4;//如果已经满足要求 就不需要替换if(cnt[Q] m cnt[W] m cnt[E] m cnt[R] m) return 0;int ans n;for(int j 0,i 0;j n;j){cnt[s[j]]--;// [i,j] 这个区间就是需要替换的while(cnt[Q] m cnt[W] m cnt[E] m cnt[R] m){ans min(ans,j-i1);cnt[s[i]];}}return ans;}
};
