【教3妹学编程-算法题】回文串重新排列查询

3妹：好冷啊， 冻得瑟瑟发抖啦
2哥 : 这已经是你今年的第几次抖啦？
3妹：昨天20度，今天7度，直降13度呢，能不抖嘛
2哥 : 继哈尔滨之后，全国各地的城市也在发展旅游业。 河北喊话赵丽颖回家呢。
3妹：哈哈哈哈，看来各地都要各显神通了。
2哥：说到回家，我有一个关于回文的题目，我们来做一下吧~
3妹：切，这个弯拐的有点急…， 不过是该题了， 一起来看一下吧

题目：

给你一个长度为 偶数 n ，下标从 0 开始的字符串 s 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ai, bi, ci, di] 。

对于每个查询 i ，你需要执行以下操作：

将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。
将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。
对于每个查询，你的任务是判断执行操作后能否让 s 变成一个 回文串 。

每个查询与其他查询都是 独立的 。

请你返回一个下标从 0 开始的数组 answer ，如果第 i 个查询执行操作后，可以将 s 变为一个回文串，那么 answer[i] = true，否则为 false 。

子字符串 指的是一个字符串中一段连续的字符序列。
s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。

示例 1：

输入：s = “abcabc”, queries = [[1,1,3,5],[0,2,5,5]]
输出：[true,true]
解释：这个例子中，有 2 个查询：
第一个查询：

• a0 = 1, b0 = 1, c0 = 3, d0 = 5
• 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
• 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。
• 现在 s 是一个回文串。所以 answer[0] = true 。
  第二个查询：
• a1 = 0, b1 = 2, c1 = 5, d1 = 5.
• 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
• 为了让 s 变为回文串，s[0:2] 可以重新排列得到 => cbaabc 。
• 现在 s 是一个回文串，所以 answer[1] = true 。
  示例 2：

输入：s = “abbcdecbba”, queries = [[0,2,7,9]]
输出：[false]
解释：这个示例中，只有一个查询。
a0 = 0, b0 = 2, c0 = 7, d0 = 9.
你可以重新排列 s[0:2] => abbcdecbba 和 s[7:9] => abbcdecbba 。
无法通过重新排列这些子字符串使 s 变为一个回文串，因为 s[3:6] 不是一个回文串。
所以 answer[0] = false 。
示例 3：

输入：s = “acbcab”, queries = [[1,2,4,5]]
输出：[true]
解释：这个示例中，只有一个查询。
a0 = 1, b0 = 2, c0 = 4, d0 = 5.
你可以重新排列 s[1:2] => acbcab 和 s[4:5] => acbcab 。
为了让 s 变为回文串，s[1:2] 可以重新排列得到 => abccab 。
然后 s[4:5] 重新排列得到 abccba 。
现在 s 是一个回文串，所以 answer[0] = true 。

提示：

2 <= n == s.length <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 4
ai == queries[i][0], bi == queries[i][1]
ci == queries[i][2], di == queries[i][3]
0 <= ai <= bi < n / 2
n / 2 <= ci <= di < n
n 是一个偶数。
s 只包含小写英文字母。

思路：

把输入的字符串记作大写 S。为方便计算，把 S 均分为左右两个字符串，其中右半部分反转。左半和右半分别记作 s 和 t。

我们需要预处理三个前缀和：

• s 的每个前缀的每个字符的出现次数，记作 sumS。
• t 的每个前缀的每个字符的出现次数，记作 sumT。
• 前缀中 s[i]≠t[i]的次数，记作 sumNe（Not Equal）。

java代码：

class Solution {
    public boolean[] canMakePalindromeQueries(String S, int[][] queries) {
        char[] s = S.toCharArray();
        int m = s.length;
        int n = m / 2;

        // 预处理三种前缀和
        int[][] sumS = new int[n + 1][26];
        for (int i = 0; i < n; i++) {
            sumS[i + 1] = sumS[i].clone();
            sumS[i + 1][s[i] - 'a']++;
        }

        int[][] sumT = new int[n + 1][26];
        for (int i = 0; i < n; i++) {
            sumT[i + 1] = sumT[i].clone();
            sumT[i + 1][s[m - 1 - i] - 'a']++;
        }

        int[] sumNe = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sumNe[i + 1] = sumNe[i] + (s[i] != s[m - 1 - i] ? 1 : 0);
        }

        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] q = queries[i];
            int l1 = q[0], r1 = q[1], l2 = m - 1 - q[3], r2 = m - 1 - q[2];
            ans[i] = l1 <= l2 ? check(l1, r1, l2, r2, sumS, sumT, sumNe) :
                                check(l2, r2, l1, r1, sumT, sumS, sumNe);
        }
        return ans;
    }

    private boolean check(int l1, int r1, int l2, int r2, int[][] sumS, int[][] sumT, int[] sumNe) {
        if (sumNe[l1] > 0 || // [0,l1-1] 有 s[i] != t[i]
            sumNe[sumNe.length - 1] - sumNe[Math.max(r1, r2) + 1] > 0) { // [max(r1,r2)+1,n-1] 有 s[i] != t[i]
            return false;
        }
        if (r2 <= r1) { // 区间包含
            return Arrays.equals(count(sumS, l1, r1), count(sumT, l1, r1));
        }
        if (r1 < l2) { // 区间不相交
            return sumNe[l2] - sumNe[r1 + 1] <= 0 && // [r1+1,l2-1] 都满足 s[i] == t[i]
                   Arrays.equals(count(sumS, l1, r1), count(sumT, l1, r1)) &&
                   Arrays.equals(count(sumS, l2, r2), count(sumT, l2, r2));
        }
        // 区间相交但不包含
        int[] s1 = subtract(count(sumS, l1, r1), count(sumT, l1, l2 - 1));
        int[] s2 = subtract(count(sumT, l2, r2), count(sumS, r1 + 1, r2));
        return s1 != null && s2 != null && Arrays.equals(s1, s2);
    }

    // 计算子串中各个字符的出现次数，闭区间 [l,r]
    private int[] count(int[][] sum, int l, int r) {
        int[] res = sum[r + 1].clone();
        for (int i = 0; i < 26; i++) {
            res[i] -= sum[l][i];
        }
        return res;
    }

    private int[] subtract(int[] s1, int[] s2) {
        for (int i = 0; i < 26; i++) {
            s1[i] -= s2[i];
            if (s1[i] < 0) {
                return null;
            }
        }
        return s1;
    }
}