寻找满足字符出现奇数次/偶数次的子串个数或者子串最长长度：前缀和+异或+哈希表
题目要求寻找某种特性的子串的数目或者最长长度，而这种特性与字符出现次数的奇偶性相关，那么可以使用前缀和+异或+哈希表解决
构建回文串检测【LC1177】
给你一个字符串
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，可以认为每次检测都是独立的）
class Solution { public List<Boolean> canMakePaliQueries(String s, int[][] queries) { // 怎么快速求出子串中每种字母的个数？ // 前缀和：存储每个字母在字符串[0,i]中出现的个数 int n = s.length(); int[][] count = new int[n + 1][26]; for (int i = 0; i < n; i++){ for (int j = 0; j < 26; j++){ count[i + 1][j] = count[i][j]; if (j == s.charAt(i) - 'a'){ count[i + 1][j]++; } } } List<Boolean> res = new ArrayList<>(); for (int[] q : queries){ int l = q[0], r = q[1], k = q[2]; int num = 0; for (int i = 0; i < 26; i++){ if ((count[r + 1][i] - count[l][i]) % 2 == 1){ num++; } } if (num / 2 <= k){ res.add(true); }else{ res.add(false); } } return res; } }
位运算
- 思路
由于只关心每种字母出现次数的奇偶性，所以不需要在前缀和中存储每种字母的出现次数，只需要保存每种字母出现次数的奇偶性。
为方便计算，用 0表示出现偶数次，用 1 表示出现奇数次。
注意只有奇数减偶数，或者偶数减奇数，才能得到奇数。所以如果相减的结果不为 0（或者说相减的两个数不相等），就表示出现了奇数次—》【异或】
作者：灵茶山艾府
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
实现
class Solution { public List<Boolean> canMakePaliQueries(String s, int[][] queries) { int n = s.length(); var sum = new int[n + 1]; for (int i = 0; i < n; i++) { int bit = 1 << (s.charAt(i) - 'a'); sum[i + 1] = sum[i] ^ bit; // 该比特对应字母的奇偶性：奇数变偶数，偶数变奇数 } var ans = new ArrayList<Boolean>(queries.length); // 预分配空间 for (var q : queries) { int left = q[0], right = q[1], k = q[2]; int m = Integer.bitCount(sum[right + 1] ^ sum[left]);// 奇数字母的个数 ans.add(m / 2 <= k); } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/2309725/yi-bu-bu-you-hua-cong-qian-zhui-he-dao-q-yh5p/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- Tips：异或可以视作「不进位加法（减法）」或者「模 222 剩余系中的加法（减法）」，所以也常常用来解决一些和奇偶性有关的问题。
每个元音包含偶数次的最长子字符串【LC1371】
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出现了偶数次。
前缀和+位运算+枚举
- 思路：
使用前缀和和位运算state记录元音字母次数的奇偶性，从大到小枚举子串长度，判断该子串是否所有元音字母都出现偶数次，如果是，那么直接返回该长度 - 实现
class Solution { public int findTheLongestSubstring(String s) { int n = s.length(); int[] sum = new int[n + 1]; for (int i = 0; i < n; i++){ if (isVowel(s.charAt(i))){ int bit = 1 << (s.charAt(i) - 'a'); sum[i + 1] = sum[i] ^ bit; }else{ sum[i + 1] = sum[i]; } } for (int len = n ; len > 0; len--){ for (int i = 0; i + len <= n; i++){ if ((sum[i + len] ^ sum[i]) == 0){ return len; } } } return 0; } public boolean isVowel(char c){ return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } }
class Solution { public int findTheLongestSubstring(String s) { int n = s.length(); Map<Integer, Integer> stateToIndex = new HashMap<>(); stateToIndex.put(0, -1); int state = 0; int res = 0; for (int i = 0; i < n; i++){ if (isVowel(s.charAt(i))){ int bit = 1 << (s.charAt(i) - 'a'); state = state ^ bit; } int l = stateToIndex.getOrDefault(state ^ 0, n); res = Math.max(res, i - l); if (!stateToIndex.containsKey(state)){ stateToIndex.put(state, i); } } return res; } public boolean isVowel(char c){ return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } }
找出最长的超赞子字符串【LC1542】
给你一个字符串
s。请返回s中最长的 超赞子字符串 的长度。「超赞子字符串」需满足满足下述两个条件：
- 该字符串是
s的一个非空子字符串- 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
前缀和+位运算+枚举【超时】
class Solution { public int longestAwesome(String s) { int n = s.length(); int[] sum = new int[n + 1]; for (int i = 0; i < n; i++){ int bit = 1 << (s.charAt(i) - '0'); sum[i + 1] = sum[i] ^ bit; } for (int len = n; len > 0; len--){ for (int i = 0; i + len <= n; i++){ int odd = Integer.bitCount(sum[i + len] ^ sum[i]); if (odd <= 1 ){ return len; } } } return 0; } }
class Solution { public int longestAwesome(String s) { // 最多有一个字符出现次数为奇数 // 最多只有一位不一样，更改每一位判断哈希表是否出现过 int n = s.length(); Map<Integer, Integer> stateToIndex = new HashMap<>(); stateToIndex.put(0, -1); int state = 0; int res = 0; for (int i = 0; i < n; i++){ int bit = 1 << (s.charAt(i) - '0'); state = state ^ bit; int l = stateToIndex.getOrDefault(state, n); res = Math.max(res, i - l); // 将某一位设置为相反 for (int j = 0; j <= 9; j++){ int b = (state >> j) & 1;// 第j个数位的值 int target = state; if (b == 1){// 将第j位设置为0 target &= ~(1 << j); }else{// 将第i位设置为1 target |= 1 << j; } l = stateToIndex.getOrDefault(target, n); res = Math.max(res, i - l); } if (!stateToIndex.containsKey(state)){ stateToIndex.put(state, i); } } return res; } }
最美子字符串的数目【LC1915】
如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。
- 例如，
"ccjjc"和"abab"都是最美字符串，但"ab"不是。
给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目*。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。*
子字符串 是字符串中的一个连续字符序列。
前缀和+位运算+哈希表
将哈希表记录坐标改为记录数目，其他同上
class Solution { public long wonderfulSubstrings(String word) { // 只有一个字母出现奇数次->异或后最多只有一位为1->target只有一位和state不同 int n = word.length(); Map<Integer, Integer> stateToCount = new HashMap<>(); stateToCount.put(0, 1); int state = 0; long res = 0L; for (int i = 0; i < n; i++){ int bit = (1 << (word.charAt(i) - 'a')); state = state ^ bit; res += stateToCount.getOrDefault(state, 0); for (int j = 0; j <= 'j' - 'a'; j++){ int b = (state >> j) & 1;// 第j个数位的值 int target = state; if (b == 1){// 将第j位设置为0 target &= ~(1 << j); }else{// 将第i位设置为1 target |= 1 << j; } res += stateToCount.getOrDefault(target, 0); } stateToCount.put(state, stateToCount.getOrDefault(state, 0) + 1); } return res; } }
class Solution { public long wonderfulSubstrings(String word) { // 只有一个字母出现奇数次->异或后最多只有一位为1->target只有一位和state不同 int n = word.length(); Map<Integer, Integer> stateToCount = new HashMap<>(); stateToCount.put(0, 1); int state = 0; long res = 0L; for (int i = 0; i < n; i++){ int bit = (1 << (word.charAt(i) - 'a')); state = state ^ bit; res += stateToCount.getOrDefault(state, 0); for (int j = 1; j < 1024; j <<= 1){ res += stateToCount.getOrDefault(state ^ j, 0); } stateToCount.put(state, stateToCount.getOrDefault(state, 0) + 1); } return res; } }
