class Solution {
public:
vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
}
};
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 <= 1051 <= queries.length <= 105queries[i].length == 4ai == queries[i][0], bi == queries[i][1]ci == queries[i][2], di == queries[i][3]0 <= ai <= bi < n / 2n / 2 <= ci <= di < n n 是一个偶数。s 只包含小写英文字母。原站题解
cpp 解法, 执行用时: 520 ms, 内存消耗: 245.2 MB, 提交时间: 2024-01-01 19:27:15
class Solution {
public:
vector<bool> canMakePalindromeQueries(string s, vector<vector<int>> &queries) {
// 分成左右两半，右半反转
int n = s.length() / 2;
string t = s.substr(n);
reverse(t.begin(), t.end());
// 预处理三种前缀和
vector<vector<int>> sum_s(n + 1, vector<int>(26));
for (int i = 0; i < n; i++) {
sum_s[i + 1] = sum_s[i];
sum_s[i + 1][s[i] - 'a']++;
}
vector<vector<int>> sum_t(n + 1, vector<int>(26));
for (int i = 0; i < n; i++) {
sum_t[i + 1] = sum_t[i];
sum_t[i + 1][t[i] - 'a']++;
}
vector<int> sum_ne(n + 1);
for (int i = 0; i < n; i++) {
sum_ne[i + 1] = sum_ne[i] + (s[i] != t[i]);
}
// 计算子串中各个字符的出现次数，闭区间 [l,r]
auto count = [](vector<vector<int>> &sum, int l, int r) -> vector<int> {
auto res = sum[r + 1];
for (int i = 0; i < 26; i++) {
res[i] -= sum[l][i];
}
return res;
};
auto subtract = [](vector<int> s1, vector<int> s2) -> vector<int> {
for (int i = 0; i < 26; i++) {
s1[i] -= s2[i];
if (s1[i] < 0) {
return {};
}
}
return s1;
};
auto check = [&](int l1, int r1, int l2, int r2, vector<vector<int>> &sumS, vector<vector<int>> &sumT) -> bool {
if (sum_ne[l1] > 0 || // [0,l1-1] 有 s[i] != t[i]
sum_ne[n] - sum_ne[max(r1, r2) + 1] > 0) { // [max(r1,r2)+1,n-1] 有 s[i] != t[i]
return false;
}
if (r2 <= r1) { // 区间包含
return count(sumS, l1, r1) == count(sumT, l1, r1);
}
if (r1 < l2) { // 区间不相交
return sum_ne[l2] - sum_ne[r1 + 1] == 0 && // [r1+1,l2-1] 都满足 s[i] == t[i]
count(sumS, l1, r1) == count(sumT, l1, r1) &&
count(sumS, l2, r2) == count(sumT, l2, r2);
}
// 区间相交但不包含
auto s1 = subtract(count(sumS, l1, r1), count(sumT, l1, l2 - 1));
auto s2 = subtract(count(sumT, l2, r2), count(sumS, r1 + 1, r2));
return !s1.empty() && !s2.empty() && s1 == s2;
};
vector<bool> ans(queries.size());
for (int i = 0; i < queries.size(); i++) {
auto &q = queries[i];
int l1 = q[0], r1 = q[1], l2 = n * 2 - 1 - q[3], r2 = n * 2 - 1 - q[2];
ans[i] = l1 <= l2 ? check(l1, r1, l2, r2, sum_s, sum_t) :
check(l2, r2, l1, r1, sum_t, sum_s);
}
return ans;
}
};
java 解法, 执行用时: 70 ms, 内存消耗: 126.1 MB, 提交时间: 2024-01-01 19:27:02
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;
}
}
golang 解法, 执行用时: 196 ms, 内存消耗: 83.2 MB, 提交时间: 2024-01-01 19:26:44
func canMakePalindromeQueries(s string, queries [][]int) []bool {
// 分成左右两半，右半反转
n := len(s) / 2
t := []byte(s[n:])
slices.Reverse(t)
s = s[:n]
// 预处理三种前缀和
sumS := make([][26]int, n+1)
for i, b := range s {
sumS[i+1] = sumS[i]
sumS[i+1][b-'a']++
}
sumT := make([][26]int, n+1)
for i, b := range t {
sumT[i+1] = sumT[i]
sumT[i+1][b-'a']++
}
sumNe := make([]int, n+1)
for i := range s {
sumNe[i+1] = sumNe[i]
if s[i] != t[i] {
sumNe[i+1]++
}
}
// 计算子串中各个字符的出现次数，闭区间 [l,r]
count := func(sum [][26]int, l, r int) []int {
res := sum[r+1]
for i, s := range sum[l][:] {
res[i] -= s
}
return res[:]
}
subtract := func(s1, s2 []int) []int {
for i, s := range s2 {
s1[i] -= s
if s1[i] < 0 {
return nil
}
}
return s1
}
check := func(l1, r1, l2, r2 int, sumS, sumT [][26]int) bool {
if sumNe[l1] > 0 || // [0,l1-1] 有 s[i] != t[i]
sumNe[n]-sumNe[max(r1, r2)+1] > 0 { // [max(r1,r2)+1,n-1] 有 s[i] != t[i]
return false
}
if r2 <= r1 { // 区间包含
return slices.Equal(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]
slices.Equal(count(sumS, l1, r1), count(sumT, l1, r1)) &&
slices.Equal(count(sumS, l2, r2), count(sumT, l2, r2))
}
// 区间相交但不包含
s1 := subtract(count(sumS, l1, r1), count(sumT, l1, l2-1))
s2 := subtract(count(sumT, l2, r2), count(sumS, r1+1, r2))
return s1 != nil && s2 != nil && slices.Equal(s1, s2)
}
ans := make([]bool, len(queries))
for i, q := range queries {
l1, r1, l2, r2 := q[0], q[1], n*2-1-q[3], n*2-1-q[2]
if l1 <= l2 {
ans[i] = check(l1, r1, l2, r2, sumS, sumT)
} else {
ans[i] = check(l2, r2, l1, r1, sumT, sumS)
}
}
return ans
}
python3 解法, 执行用时: 692 ms, 内存消耗: 77.5 MB, 提交时间: 2024-01-01 19:26:28
class Solution:
def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
# 分成左右两半，右半反转
n = len(s) // 2
t = s[n:][::-1]
s = s[:n]
# 预处理三种前缀和
sum_s = [[0] * 26 for _ in range(n + 1)]
for i, b in enumerate(s):
sum_s[i + 1] = sum_s[i][:]
sum_s[i + 1][ord(b) - ord('a')] += 1
sum_t = [[0] * 26 for _ in range(n + 1)]
for i, b in enumerate(t):
sum_t[i + 1] = sum_t[i][:]
sum_t[i + 1][ord(b) - ord('a')] += 1
sum_ne = list(accumulate((x != y for x, y in zip(s, t)), initial=0))
# 计算子串中各个字符的出现次数，闭区间 [l,r]
def count(sum: List[List[int]], l: int, r: int) -> List[int]:
return [x - y for x, y in zip(sum[r + 1], sum[l])]
def subtract(s1: List[int], s2: List[int]) -> List[int]:
for i, s in enumerate(s2):
s1[i] -= s
if s1[i] < 0:
return False
return s1
def check(l1: int, r1: int, l2: int, r2: int, sumS: List[List[int]], sumT: List[List[int]]) -> bool:
# [0,l1-1] 有 s[i] != t[i] 或者 [max(r1,r2)+1,n-1] 有 s[i] != t[i]
if sum_ne[l1] > 0 or sum_ne[n] - sum_ne[max(r1, r2) + 1] > 0:
return False
if r2 <= r1: # 区间包含
return count(sumS, l1, r1) == count(sumT, l1, r1)
if r1 < l2: # 区间不相交
# [r1+1,l2-1] 都满足 s[i] == t[i]
return sum_ne[l2] - sum_ne[r1 + 1] == 0 and \
count(sumS, l1, r1) == count(sumT, l1, r1) and \
count(sumS, l2, r2) == count(sumT, l2, r2)
# 区间相交但不包含
s1 = subtract(count(sumS, l1, r1), count(sumT, l1, l2 - 1))
s2 = subtract(count(sumT, l2, r2), count(sumS, r1 + 1, r2))
return s1 and s2 and s1 == s2
ans = [False] * len(queries)
for i, (l1, r1, c, d) in enumerate(queries):
l2, r2 = n * 2 - 1 - d, n * 2 - 1 - c
ans[i] = check(l1, r1, l2, r2, sum_s, sum_t) if l1 <= l2 else \
check(l2, r2, l1, r1, sum_t, sum_s)
return ans