题目描述
给你一个长度为 偶数 n
,下标从 0 开始的字符串 s
。
同时给你一个下标从 0 开始的二维整数数组 queries
,其中 queries[i] = [a_i, b_i, c_i, d_i]
。
对于每个查询 i
,你需要执行以下操作:
- 将下标在范围
0 <= ai <= bi < n / 2
内的 子字符串s[a_i:b_i]
中的字符重新排列。 - 将下标在范围
n / 2 <= ci <= di < n
内的 子字符串s[c_i:d_i]
中的字符重新排列。
对于每个查询,你的任务是判断执行操作后能否让 s
变成一个 回文串。
每个查询与其他查询都是 独立的。
请你返回一个下标从 0 开始的数组 answer
,如果第 i
个查询执行操作后,可以将 s
变为一个回文串,那么 answer[i] = true
,否则为 false
。
- 子字符串 指的是一个字符串中一段连续的字符序列。
s[x:y]
表示s
中从下标x
到y
且两个端点 都包含 的子字符串。
样例
输入: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。
输入: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。
输入: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
a_i == queries[i][0], b_i == queries[i][1]
c_i == queries[i][2], d_i == queries[i][3]
0 <= a_i <= b_i < n / 2
n / 2 <= c_i <= d_i < n
n
是一个偶数。s
只包含小写英文字母。
算法
(思维题) $O((n + q)|\Sigma|)$
- 将原始字符串的后半段翻转,相应的询问也翻转,方便处理下标。
- 考察一个询问 $(a, b)$ 和 $(c, d)$。$(a, b)$ 在 后半段 的对应区间为 $(a’, b’)$,$(c, d)$ 在 前半段 的对应区间为 $(c’, d’)$。
- 对于前半段,不在 $(a, b)$ 和 $(c’, d’)$ 内的区间,需要保证字符与后半段对应的字符相同。这部分判定可以通过预处理前半段的一个前缀和数组 $eq$,即 $eq(i) = eq(i - 1) + (s(i) == s(i + n / 2))$。
- 对于在 $(a, b)$ 和 $(c’, d’)$ 内的区间:
- 如果 $(a, b)$ 和 $(c’, d’)$ 没有重叠,则需要判定 $(a, b)$ 与 $(a’, b’)$ 字符出现情况是否相同,以及 $(c, d)$ 与 $(c’, d’)$ 字符出现情况是否相同。
- 如果 $(a, b)$ 和 $(c’, d’)$ 有包含关系,则仅需要判定较大区间与对应另一段区间内,字符出现情况是否相同。
- 其他情况,即重叠,但不包含,不妨假设区间的关系为 $a < c’ < b < d’$(另一种情况与此类似),则需要判定 $(a, d’)$ 和后半段对应区间的字符出现情况相同,并且,还需要判定 $(a, b)$ 的字符出现情况 大于等于 $(a, c - 1)$,且 $(c, d)$ 的字符出现情况 大于等于 $(b’ + 1, d)$。
- 针对 4 的判定,需要预处理前缀每种字符的出现次数。
时间复杂度
- 预处理的时间复杂度为 $O(n |\Sigma|)$。
- 对于每个询问,仅需要 $O(|\Sigma|)$ 的时间判定。
- 故总时间复杂度为 $O((n + q)|\Sigma|)$。
空间复杂度
- 需要 $O(n|\Sigma| + q)$ 的额外空间存储预处理数组和答案。
C++ 代码
const int N = 100010;
int cnt[N][26], eq[N];
class Solution {
private:
int n, nn;
bool eq1(int l, int r) {
if (l > r)
return true;
return (eq[r] - (l == 0 ? 0 : eq[l - 1])) == r - l + 1;
}
bool eq2(int l, int r) {
if (l > r)
return true;
for (int i = 0; i < 26; i++)
if (cnt[r][i] - (l == 0 ? 0 : cnt[l - 1][i]) !=
cnt[r + nn][i] - cnt[l + nn - 1][i]
)
return false;
return true;
}
bool ge2(int l1, int r1, int l2, int r2) {
if (l1 > r1)
return l2 > r2;
if (l2 > r2 && l1 > r1)
return true;
for (int i = 0; i < 26; i++)
if (cnt[r1][i] - (l1 == 0 ? 0 : cnt[l1 - 1][i]) <
cnt[r2][i] - (l2 == 0 ? 0 : cnt[l2 - 1][i])
)
return false;
return true;
}
bool check(int a, int b, int c, int d) {
int ta = a, tb = b, tc = c - nn, td = d - nn;
if (ta > tc) {
swap(ta, tc);
swap(tb, td);
}
if (tb >= tc) {
if (!(eq1(0, ta - 1) && eq1(max(tb, td) + 1, nn - 1)))
return false;
if (ta == tc || tb >= td)
return eq2(ta, max(tb, td));
if (!eq2(ta, td))
return false;
if (a < c - nn)
return ge2(a, b, a + nn, c - 1) && ge2(c, d, b + 1, d - nn);
return ge2(a, b, d + 1, b + nn) && ge2(c, d, c - nn, a - 1);
}
return eq1(0, ta - 1) && eq1(tb + 1, tc - 1) && eq1(td + 1, nn - 1)
&& eq2(ta, tb) && eq2(tc, td);
}
public:
vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {
n = s.size(); nn = n / 2;
for (int i = nn, j = n - 1; i < j; i++, j--)
swap(s[i], s[j]);
eq[0] = s[0] == s[nn];
for (int i = 1; i < nn; i++)
eq[i] = eq[i - 1] + (s[i] == s[i + nn]);
memset(cnt[0], 0, sizeof(cnt[0]));
cnt[0][s[0] - 'a'] = 1;
for (int i = 1; i < n; i++) {
memcpy(cnt[i], cnt[i - 1], sizeof(cnt[i]));
++cnt[i][s[i] - 'a'];
}
vector<bool> ans;
for (const auto &q : queries) {
int a = q[0], b = q[1];
int c = n + nn - q[3] - 1, d = n + nn - q[2] - 1;
ans.push_back(check(a, b, c, d));
}
return ans;
}
};