本文涉及的基础知识点

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);
		}