回文串重新排列查询

题目

2983. 回文串重新排列查询

---

给你一个长度为 偶数 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对半分开成两个串s1,s2。并s2反转。

将查询的$a_i,b_i,c_i,d_i$重新编号为s1和s2的索引。

若[a,b]为s1可以调整的区间，若[c,d]为s2可以调整的区间。若$a < c < b < d$，两个区间存在交集。

对于s2[a,c-1]来说是无法修改的，只能从s1[a,b]中选取对应成为回文串的字符。
同样的，对于s1[b+1,d]来说是无法修改的，只能从s2[c,d]中选取对应成为回文串的字符。

当把非交集部分安排好后，交集的部分只要出现的字符相同则可以成为回文。

此外，还有一个前提条件就是，两个区间的并集必须包含所有下标i，满足s1[i] != s2[i]。如果存在对称位置字符不同，操作的区间不包含这个位置，那么无论怎么操作也无法成为回文串。

代码

class Solution {
public:
    vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
        int sz = s.size();
        int n = sz/2;
        string s1, s2;
        for (int i=0; i<n; i++) s1.push_back(s[i]);
        for (int i=sz-1; i>=n; i--) s2.push_back(s[i]);
        vector<vector<int>> g(n+1, vector<int>(26)), h(n+1, vector<int>(26));
        for (int i=1; i<=n; i++) {
            for (int j=0; j<26; j++) g[i][j] = g[i-1][j], h[i][j] = h[i-1][j];
            g[i][s1[i-1]-'a']++;
            h[i][s2[i-1]-'a']++;
        }
        vector<int> dif(n+1);
        for (int i=1; i<=n; i++) {
            dif[i] += dif[i-1] + (s1[i-1] != s2[i-1]);
        }
        auto sol = [&](vector<int>& q) {
            int a=q[0]+1, b=q[1]+1, c=2*n-q[3], d=2*n-q[2];
            vector<pair<int,int>> crs, dep1, dep2;
            if (max(a,c) <= min(b,d)) crs.emplace_back(max(a,c), min(b,d));
            if (crs.size()) {
                if (a<c) dep1.emplace_back(a,c-1);
                if (c<a) dep2.emplace_back(c,a-1);
                if (d<b) dep1.emplace_back(d+1,b);
                if (b<d) dep2.emplace_back(b+1,d);
            } else {
                dep1.emplace_back(a,b);
                dep2.emplace_back(c,d);
            }
            int res = dif[n];
            auto cpu = [&](vector<pair<int,int>>& v) {
                for (auto& [i,j]:v) {
                    res-=dif[j]-dif[i-1];
                }
            };
            cpu(crs),cpu(dep1),cpu(dep2);
            if (res>0) return false;
            vector<int> r1(26), r2(26);
            for (int i=0; i<26; i++) {
                r1[i] = g[b][i]-g[a-1][i];
                r2[i] = h[d][i]-h[c-1][i];
            }
            for (auto [i,j]:dep1) {
                for (int k=0; k<26; k++) {
                    r1[k] -= h[j][k]-h[i-1][k];
                }
            }
            for (auto [i,j]:dep2) {
                for (int k=0; k<26; k++) {
                    r2[k] -= g[j][k]-g[i-1][k];
                }
            }
            for (int i=0; i<26; i++) {
                if (r1[i]<0 || r2[i]<0 || r1[i]!=r2[i]) return false;
            }
            return true;
        };
        vector<bool> ans;
        for (auto& i:queries) {
            ans.push_back(sol(i));
        }
        return ans;
    }
};