本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
位运算、状态压缩、枚举子集汇总

LeetCode 1177. 构建回文串检测

难度分：1848
给你一个字符串 s，请你对 s 的子串进行检测。
每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], …, s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left…right] = “aaa” 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
示例：
输入：s = “abcda”, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = “d”，回文。
queries[1] : 子串 = “bc”，不是回文。
queries[2] : 子串 = “abcd”，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = “abcd”，可以变成回文的 “abba”。 也可以变成 “baab”，先重新排序变成 “bacd”，然后把 “cd” 替换为 “ab”。
queries[4] : 子串 = “abcda”，可以变成回文的 “abcba”。
提示：
1 <= s.length, queries.length <= 10⁵
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

前缀和

令s[left…right]数量为奇数的字符数量为m，如果 m <= 2$\times$k + 1 。唯一的奇数字符放到中间。
preSum[i] 记录字符‘a’+1 的数量的前缀和，由于只关注奇偶性，所以偶数统一为0，奇数统一为1。
利用状态压缩将preSum[0…25][j]压缩成p[j]

代码

核心代码

class Solution {
		public:
			vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
				int iMask = 0;
				vector<int> vMask(1);
				for (auto& ch : s)
				{
					iMask ^= (1 << (ch - 'a'));
					vMask.push_back(iMask);
				}

				vector<bool> vRet;
				for (auto& v : queries)
				{
					int iMask = vMask[v[1] + 1] ^ vMask[v[0]];
					int iBitCnt = bitcount(iMask);
					vRet.push_back(iBitCnt / 2 <= v[2]);
				}
				return vRet;
			}
			//通过 x &= (x-1)实现
			int bitcount(unsigned x) {
				int countx = 0;
				while (x) {
					countx++;
					x &= (x - 1);
				}
				return countx;
			}
		};

单元测试

	string s;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			s = "abcda", queries = { {3,3,0},{1,2,0},{0,3,1},{0,3,2},{0,4,1} };
			auto res = Solution().canMakePaliQueries(s, queries);
			AssertEx({ true,false,false,true,true }, res);
		}