建设一个行业性的网站价格,南平 网站建设,手机开发者选项在哪里找,在线定制平台来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
有一个只含有 Q, W, E, R 四种字符#xff0c;且长度为 n 的字符串。
假如在该字符串中#xff0c;这四个字符都恰好出现 n/4 次#xff0c;那么它就是一个「平衡字符串」。
给你一个这样的字符…来源力扣LeetCode
描述
有一个只含有 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。提示
1 s.length 105s.length 是 4 的倍数s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符
方法滑动窗口
思路与算法
设 partial n / 4 我们选择 s 的一个子串作为「待替换子串」只有当 s 剩余的部分中 ‘Q’‘W’‘E’‘R’ 的出现次数都小于等于 partial 时我们才有可能使 s 变为「平衡字符串」。
如果原始的 s 就是 「平衡字符串」我们直接返回 0否则我们按照以下思路求解。
从小到大枚举「待替换子串」的左端点 l为了使得替换的长度最小我们要找到最近的右端点 r使得去除 [l, r) 之后的剩余部分满足上述条件。不难发现随着 l 的递增r 也是递增的。
具体的我们使用滑动窗口来维护区间 [l, r) 之外的剩余部分中 ‘Q’‘W’‘E’‘R’ 的出现次数当其中一种字符的出现次数大于 partial 时令 s[r] 的出现次数减 1并使得 r 向右移动一个单位。该操作一直被执行直到条件被满足或者 r 到达 s 的末尾。
如果找到了使得条件被满足的 r我们用 r − l 来更新答案然后令 s[l] 的出现次数加 1并使得 l 向右移动一个单位进行下一次枚举。否则后序的 l 也将不会有合法的 r此时我们可以直接跳出循环。对于所有合法的 [l, r)取 r − l 的最小值做为答案。
代码
class Solution {
public:int idx(const char c) {return c - A;}int balancedString(string s) {vectorint cnt(26);for (auto c : s) {cnt[idx(c)];}int partial s.size() / 4;int res s.size();auto check []() {if (cnt[idx(Q)] partial || cnt[idx(W)] partial \|| cnt[idx(E)] partial || cnt[idx(R)] partial) {return false;}return true;};if (check()) {return 0;}for (int l 0, r 0; l s.size(); l) {while (r s.size() !check()) {cnt[idx(s[r])]--;r;}if (!check()) {break;}res min(res, r - l);cnt[idx(s[l])];}return res;}
};执行用时20 ms, 在所有 C 提交中击败了67.46%的用户 内存消耗7.6 MB, 在所有 C 提交中击败了83.33%的用户 复杂度分析 时间复杂度O(n)其中 n 为 s 的长度。 空间复杂度O(∣Σ∣)其中 ∣Σ∣ 表示字符集大小在本题中 ∣Σ∣ 26。 authorLeetCode-Solution
