构建回文串检测【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，可以认为每次检测都是独立的）
前缀和
- 思路
由于可以将子串重新排列，那么重新排列后能否构成回文串取决于子串中奇数个字母的数目num - 偶数个字母可以在回文串头尾各放一个，因此可以忽略
- 将个数为奇数的字母一半替换成其他字母，如果num为奇数，剩余的一个可以放在中间，那么需要替换⌊num/2⌋个字母如果暴力求出子串中奇数个字母的数目，时间复杂度为O ( n 2 ) 会超时，优化思路为使用前缀和数组预处理每个字母的数量，那么能快算求出子串中奇数个字母的数目
- 实现
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; } }
复杂度
- 时间复杂度：O((n+q)C)
- 空间复杂度：O ( n C )
