以下是 LeetCode 2983. 回文串重新排列查询 的 Java 实现核心思路是将字符串分成两半对右半部分反转后进行前缀和预处理然后对每个查询进行分类讨论。核心思路1. 对称处理将字符串 s 分为左右两半右半部分反转后与左半部分对齐2. 前缀和预处理两个前缀和数组分别记录左半和反转后右半的字符频次3. 差异数组预处理 diff[i] 表示前 i 个位置中左右两半对应位置字符不同的个数4. 查询分类对于每个查询根据两个区间 [a,b] 和 [c,d]映射到左半部分后的位置关系分为三种情况- 包含关系一个区间完全包含另一个- 不相交两个区间没有交集- 相交但不包含需要计算各自多出的字符是否能互相匹配Java 代码javaclass Solution {public boolean[] canMakePalindromeQueries(String s, int[][] queries) {int n s.length();int m n / 2;// 左半部分String left s.substring(0, m);// 右半部分反转使其与左半部分对称位置对齐String rightReversed new StringBuilder(s.substring(m)).reverse().toString();// pre1[i][c] left[0..i-1] 中字符 c 的出现次数// pre2[i][c] rightReversed[0..i-1] 中字符 c 的出现次数int[][] pre1 new int[m 1][26];int[][] pre2 new int[m 1][26];// diff[i] 前 i 个位置中left[j] ! rightReversed[j] 的个数int[] diff new int[m 1];for (int i 1; i m; i) {// 复制前一个状态System.arraycopy(pre1[i - 1], 0, pre1[i], 0, 26);System.arraycopy(pre2[i - 1], 0, pre2[i], 0, 26);// 更新当前字符计数pre1[i][left.charAt(i - 1) - a];pre2[i][rightReversed.charAt(i - 1) - a];// 更新不匹配计数diff[i] diff[i - 1] (left.charAt(i - 1) rightReversed.charAt(i - 1) ? 0 : 1);}boolean[] ans new boolean[queries.length];for (int i 0; i queries.length; i) {int[] q queries[i];int a q[0], b q[1];// 将右半部分的查询映射到反转后的坐标// 原字符串中 s[c..d] 对应反转后 rightReversed[n-1-d .. n-1-c]int c n - 1 - q[3];int d n - 1 - q[2];// 保证 a c方便统一处理if (a c) {ans[i] check(pre1, pre2, diff, a, b, c, d);} else {ans[i] check(pre2, pre1, diff, c, d, a, b);}}return ans;}/*** 检查查询是否可行* 假设 a c即第一个区间在第二个区间左边或重合** param pre1 第一个字符串对应 left的前缀和* param pre2 第二个字符串对应 rightReversed的前缀和* param diff 不匹配前缀和数组* param a,b 第一个区间 [a,b]在 pre1 对应的字符串上* param c,d 第二个区间 [c,d]在 pre2 对应的字符串上且 a c*/private boolean check(int[][] pre1, int[][] pre2, int[] diff,int a, int b, int c, int d) {// 条件1[0, a-1] 和 [max(b,d)1, m-1] 必须已经匹配无法修改的部分// diff[a] 0 表示 [0, a-1] 中有不匹配// diff[m] - diff[max(b,d)1] 0 表示 [max(b,d)1, m-1] 中有不匹配if (diff[a] 0 || diff[diff.length - 1] - diff[Math.max(b, d) 1] 0) {return false;}// 情况1第二个区间完全包含在第一个区间内d b// 此时两个可重排区间的并集就是 [a,b]// 需要 [a,b] 中 pre1 和 pre2 的字符频次相同if (d b) {return Arrays.equals(count(pre1, a, b), count(pre2, a, b));}// 情况2两个区间不相交b c// 需要中间部分 [b1, c-1] 已经匹配且两个区间各自内部字符频次匹配if (b c) {return diff[c] - diff[b 1] 0 Arrays.equals(count(pre1, a, b), count(pre2, a, b)) Arrays.equals(count(pre1, c, d), count(pre2, c, d));}// 情况3两个区间相交但不包含c b d// 需要计算各自多出的字符是否能互补// pre1 在 [a,b] 中多出的部分 [a,b] 的字符 - [a,c-1] 的字符这部分 pre2 已经匹配// pre2 在 [c,d] 中多出的部分 [c,d] 的字符 - [b1,d] 的字符这部分 pre1 已经匹配int[] cnt1 sub(count(pre1, a, b), count(pre2, a, c - 1));int[] cnt2 sub(count(pre2, c, d), count(pre1, b 1, d));// 如果减法出现负数说明无法匹配否则需要 cnt1 cnt2return cnt1 ! null cnt2 ! null Arrays.equals(cnt1, cnt2);}/*** 计算区间 [l, r] 的字符频次闭区间*/private int[] count(int[][] pre, int l, int r) {int[] res new int[26];for (int i 0; i 26; i) {res[i] pre[r 1][i] - pre[l][i];}return res;}/*** 数组减法 a - b如果出现负数返回 null*/private int[] sub(int[] a, int[] b) {int[] res new int[26];for (int i 0; i 26; i) {res[i] a[i] - b[i];if (res[i] 0) {return null;}}return res;}}复杂度分析- 时间复杂度O((n q) \times |\Sigma|)其中 n 是字符串长度q 是查询数量|\Sigma| 26 为字符集大小- 空间复杂度O(n \times |\Sigma|)用于存储前缀和数组关键点说明要点 说明右半反转 将 s[n/2..n-1] 反转后位置 i 和 n-1-i 对应回文的对称位置查询映射 c n-1-d, d n-1-c将右半查询映射到反转后的坐标系不可变区域 查询区间之外的位置必须已经对称匹配否则无法通过重排修复相交处理 当两个可重排区间相交时各自独有的部分必须字符频次相同才能互补