【C++滑动窗口】1234. 替换子串得到平衡字符串|1877

本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode1234. 替换子串得到平衡字符串

有一个只含有 ‘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 <= 10⁵
s.length 是 4 的倍数
s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符

滑动窗口

将QWER替换成abcd。c2[i]记录’a’+i的数量-n/4。
c1[i]记录s[i…j-1]中’a’+i的数量。如果c[i]的数量全部大于c2[i]，则替换掉s[i…j-1]便是平衡字符串。则j-i就是以i开头的最优解。
造作步骤：
一，如果c2[i]为正数，则将c2[i]个’a’+i转成x。转化后’a’+i变得平衡。
二，如果c2[i]为负数，则x转化成’a’+i，转化后’a’+i变得平衡。
注意：i不一定有对应的解，比如：aaaaabcd ，比如长度为5的后缀没有3个a。所以还要判断是否合法，才更新ans。

代码

核心代码

class Solution {public:int balancedString(string s) {unordered_map<char, char> mReplace = { {'Q','a'},{'W','b'} ,{'E','c'} ,{'R','d'} };const int N = s.length();int c1[4] = { 0 }, c2[4] = { -N/4,-N / 4,-N / 4,-N / 4 };for (auto& ch : s) {ch = mReplace[ch];c2[ch - 'a']++;}auto Is = [&]() {return (c1[0] >= c2[0]) && (c1[1] >= c2[1]) && (c1[2] >= c2[2]) && (c1[3] >= c2[3]); };int ans = N;for (int i = 0, j = 0; i < s.length(); i++) {while (j < s.length()&&!Is()) {c1[s[j] - 'a']++; j++;}if (Is()) { ans = min(ans, j - i); }					c1[s[i] - 'a']--;}return ans;}};

单元测试

string s;TEST_METHOD(TestMethod11){s = "QWER";auto res = Solution().balancedString(s);AssertEx(0, res);}TEST_METHOD(TestMethod12){s = "QQWE";auto res = Solution().balancedString(s);AssertEx(1, res);}TEST_METHOD(TestMethod13){s = "QQQW";auto res = Solution().balancedString(s);AssertEx(2, res);}TEST_METHOD(TestMethod14){s = "QQQQ";auto res = Solution().balancedString(s);AssertEx(3, res);}TEST_METHOD(TestMethod15){s = "WWEQERQWQWWRWWERQWEQ";auto res = Solution().balancedString(s);AssertEx(4, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功