2983. Palindrome Rearrangement Queries LeetCode Solution
In this guide, you will get 2983. Palindrome Rearrangement Queries LeetCode Solution with the best time and space complexity. The solution to Palindrome Rearrangement Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Palindrome Rearrangement Queries solution in C++
- Palindrome Rearrangement Queries solution in Java
- Palindrome Rearrangement Queries solution in Python
- Additional Resources
Problem Statement of Palindrome Rearrangement Queries
You are given a 0-indexed string s having an even length n.
You are also given a 0-indexed 2D integer array, queries, where queries[i] = [ai, bi, ci, di].
For each query i, you are allowed to perform the following operations:
Rearrange the characters within the substring s[ai:bi], where 0 <= ai <= bi < n / 2.
Rearrange the characters within the substring s[ci:di], where n / 2 <= ci <= di < n.
For each query, your task is to determine whether it is possible to make s a palindrome by performing the operations.
Each query is answered independently of the others.
Return a 0-indexed array answer, where answer[i] == true if it is possible to make s a palindrome by performing operations specified by the ith query, and false otherwise.
A substring is a contiguous sequence of characters within a string.
s[x:y] represents the substring consisting of characters from the index x to index y in s, both inclusive.
Example 1:
Input: s = “abcabc”, queries = [[1,1,3,5],[0,2,5,5]]
Output: [true,true]
Explanation: In this example, there are two queries:
In the first query:
– a0 = 1, b0 = 1, c0 = 3, d0 = 5.
– So, you are allowed to rearrange s[1:1] => abcabc and s[3:5] => abcabc.
– To make s a palindrome, s[3:5] can be rearranged to become => abccba.
– Now, s is a palindrome. So, answer[0] = true.
In the second query:
– a1 = 0, b1 = 2, c1 = 5, d1 = 5.
– So, you are allowed to rearrange s[0:2] => abcabc and s[5:5] => abcabc.
– To make s a palindrome, s[0:2] can be rearranged to become => cbaabc.
– Now, s is a palindrome. So, answer[1] = true.
Example 2:
Input: s = “abbcdecbba”, queries = [[0,2,7,9]]
Output: [false]
Explanation: In this example, there is only one query.
a0 = 0, b0 = 2, c0 = 7, d0 = 9.
So, you are allowed to rearrange s[0:2] => abbcdecbba and s[7:9] => abbcdecbba.
It is not possible to make s a palindrome by rearranging these substrings because s[3:6] is not a palindrome.
So, answer[0] = false.
Example 3:
Input: s = “acbcab”, queries = [[1,2,4,5]]
Output: [true]
Explanation: In this example, there is only one query.
a0 = 1, b0 = 2, c0 = 4, d0 = 5.
So, you are allowed to rearrange s[1:2] => acbcab and s[4:5] => acbcab.
To make s a palindrome s[1:2] can be rearranged to become abccab.
Then, s[4:5] can be rearranged to become abccba.
Now, s is a palindrome. So, answer[0] = true.
Constraints:
2 <= n == s.length <= 105
1 <= queries.length <= 105
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 is even.
s consists of only lowercase English letters.
Complexity Analysis
- Time Complexity: O(26n) = O(n)
- Space Complexity: O(26n) = O(n)
2983. Palindrome Rearrangement Queries LeetCode Solution in C++
class Solution {
public:
vector<bool> canMakePalindromeQueries(string s,
vector<vector<int>>& queries) {
const int n = s.length();
// mirroredDiffs[i] := the number of different letters between the first i
// letters of s[0..n / 2) and the first i letters of s[n / 2..n)[::-1]
const vector<int> mirroredDiffs = getMirroredDiffs(s);
// counts[i] := the count of s[0..i)
const vector<vector<int>> counts = getCounts(s);
vector<bool> ans;
for (const vector<int>& query : queries) {
// Use left-closed, right-open intervals to facilitate the calculation.
// ...... [a, b) ...|... [rb, ra) ......
// .... [rd, rc) .....|..... [c, d) ....
const int a = query[0];
const int b = query[1] + 1;
const int c = query[2];
const int d = query[3] + 1;
const int ra = n - a; // the reflected index of a in s[n / 2..n)
const int rb = n - b; // the reflected index of b in s[n / 2..n)
const int rc = n - c; // the reflected index of c in s[n / 2..n)
const int rd = n - d; // the reflected index of d in s[n / 2..n)
// No difference is allowed outside the query ranges.
if (min(a, rd) > 0 && mirroredDiffs[min(a, rd)] > 0 ||
n / 2 > max(b, rc) &&
mirroredDiffs[n / 2] - mirroredDiffs[max(b, rc)] > 0 ||
rd > b && mirroredDiffs[rd] - mirroredDiffs[b] > 0 ||
a > rc && mirroredDiffs[a] - mirroredDiffs[rc] > 0) {
ans.push_back(false);
} else {
// The `count` map of the intersection of [a, b) and [rd, rc) in
// s[0..n / 2) must equate to the `count` map of the intersection of
// [c, d) and [rb, ra) in s[n / 2..n).
vector<int> leftRangeCount = subtractArrays(counts[b], counts[a]);
vector<int> rightRangeCount = subtractArrays(counts[d], counts[c]);
if (a > rd)
rightRangeCount = subtractArrays(
rightRangeCount, subtractArrays(counts[min(a, rc)], counts[rd]));
if (rc > b)
rightRangeCount = subtractArrays(
rightRangeCount, subtractArrays(counts[rc], counts[max(b, rd)]));
if (c > rb)
leftRangeCount = subtractArrays(
leftRangeCount, subtractArrays(counts[min(c, ra)], counts[rb]));
if (ra > d)
leftRangeCount = subtractArrays(
leftRangeCount, subtractArrays(counts[ra], counts[max(d, rb)]));
ans.push_back(ranges::all_of(leftRangeCount, [](int freq) {
return freq >= 0;
}) && ranges::all_of(rightRangeCount, [](int freq) {
return freq >= 0;
}) && leftRangeCount == rightRangeCount);
}
}
return ans;
}
private:
vector<int> getMirroredDiffs(const string& s) {
vector<int> diffs(1);
for (int i = 0, j = s.length() - 1; i < j; ++i, --j)
diffs.push_back(diffs.back() + (s[i] != s[j] ? 1 : 0));
return diffs;
}
vector<vector<int>> getCounts(const string& s) {
vector<int> count(26);
vector<vector<int>> counts{count};
for (const char c : s) {
++count[c - 'a'];
counts.push_back(count);
}
return counts;
}
vector<int> subtractArrays(const vector<int>& a, const vector<int>& b) {
vector<int> res;
for (int i = 0; i < a.size(); ++i)
res.push_back(a[i] - b[i]);
return res;
}
};
/* code provided by PROGIEZ */2983. Palindrome Rearrangement Queries LeetCode Solution in Java
class Solution {
public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
final int n = s.length();
// mirroredDiffs[i] := the number of different letters between the first i
// letters of s[0..n / 2) and the first i letters of s[n / 2..n)[::-1]
final int[] mirroredDiffs = getMirroredDiffs(s);
// counts[i] := the count of s[0..i)
final int[][] counts = getCounts(s);
boolean[] ans = new boolean[queries.length];
for (int i = 0; i < queries.length; i++) {
// Use left-closed, right-open intervals to facilitate the calculation.
// ...... [a, b) ...|... [rb, ra) ......
// .... [rd, rc) .....|..... [c, d) ....
int[] query = queries[i];
final int a = query[0];
final int b = query[1] + 1;
final int c = query[2];
final int d = query[3] + 1;
final int ra = n - a; // the reflected index of a in s[n / 2..n)
final int rb = n - b; // the reflected index of b in s[n / 2..n)
final int rc = n - c; // the reflected index of c in s[n / 2..n)
final int rd = n - d; // the reflected index of d in s[n / 2..n)
// No difference is allowed outside the query ranges.
if ((Math.min(a, rd) > 0 && mirroredDiffs[Math.min(a, rd)] > 0) ||
(n / 2 > Math.max(b, rc) && mirroredDiffs[n / 2] - mirroredDiffs[Math.max(b, rc)] > 0) ||
(rd > b && mirroredDiffs[rd] - mirroredDiffs[b] > 0) ||
(a > rc && mirroredDiffs[a] - mirroredDiffs[rc] > 0)) {
ans[i] = false;
} else {
// The `count` map of the intersection of [a, b) and [rd, rc) in
// s[0..n / 2) must equate to the `count` map of the intersection of
// [c, d) and [rb, ra) in s[n / 2..n).
int[] leftRangeCount = subtractArrays(counts[b], counts[a]);
int[] rightRangeCount = subtractArrays(counts[d], counts[c]);
if (a > rd)
rightRangeCount =
subtractArrays(rightRangeCount, subtractArrays(counts[Math.min(a, rc)], counts[rd]));
if (rc > b)
rightRangeCount =
subtractArrays(rightRangeCount, subtractArrays(counts[rc], counts[Math.max(b, rd)]));
if (c > rb)
leftRangeCount =
subtractArrays(leftRangeCount, subtractArrays(counts[Math.min(c, ra)], counts[rb]));
if (ra > d)
leftRangeCount =
subtractArrays(leftRangeCount, subtractArrays(counts[ra], counts[Math.max(d, rb)]));
ans[i] = Arrays.stream(leftRangeCount).allMatch(freq -> freq >= 0) &&
Arrays.stream(rightRangeCount).allMatch(freq -> freq >= 0) &&
Arrays.equals(leftRangeCount, rightRangeCount);
}
}
return ans;
}
private int[] getMirroredDiffs(final String s) {
int[] diffs = new int[s.length() / 2 + 1];
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
diffs[i + 1] = diffs[i] + (s.charAt(i) != s.charAt(j) ? 1 : 0);
}
return diffs;
}
private int[][] getCounts(final String s) {
int[][] counts = new int[s.length() + 1][26];
int[] count = new int[26];
for (int i = 0; i < s.length(); ++i) {
++count[s.charAt(i) - 'a'];
System.arraycopy(count, 0, counts[i + 1], 0, 26);
}
return counts;
}
private int[] subtractArrays(int[] a, int[] b) {
int[] res = new int[a.length];
for (int i = 0; i < a.length; ++i)
res[i] = a[i] - b[i];
return res;
}
}
// code provided by PROGIEZ2983. Palindrome Rearrangement Queries LeetCode Solution in Python
class Solution:
def canMakePalindromeQueries(
self,
s: str,
queries: list[list[int]],
) -> list[bool]:
n = len(s)
# mirroredDiffs[i] := the number of different letters between the first i
# letters of s[0..n / 2) and the first i letters of s[n / 2..n)[::-1]
mirroredDiffs = self._getMirroredDiffs(s)
# counts[i] := the count of s[0..i)
counts = self._getCounts(s)
ans = []
def subtractArrays(a: list[int], b: list[int]):
return [x - y for x, y in zip(a, b)]
for a, b, c, d in queries:
# Use left-closed, right-open intervals to facilitate the calculation.
# ...... [a, b) ...|... [rb, ra) ......
# .... [rd, rc) .....|..... [c, d) ....
b += 1
d += 1
ra = n - a # the reflected index of a in s[n / 2..n)
rb = n - b # the reflected index of b in s[n / 2..n)
rc = n - c # the reflected index of c in s[n / 2..n)
rd = n - d # the reflected index of d in s[n / 2..n)
# No difference is allowed outside the query ranges.
if ((min(a, rd) > 0 and mirroredDiffs[min(a, rd)] > 0) or
(n // 2 > max(b, rc) and
mirroredDiffs[n // 2] - mirroredDiffs[max(b, rc)] > 0) or
(rd > b and mirroredDiffs[rd] - mirroredDiffs[b] > 0) or
(a > rc and mirroredDiffs[a] - mirroredDiffs[rc] > 0)):
ans.append(False)
else:
# The `count` map of the intersection of [a, b) and [rd, rc) in
# s[0..n / 2) must equate to the `count` map of the intersection of
# [c, d) and [rb, ra) in s[n / 2..n).
leftRangeCount = subtractArrays(counts[b], counts[a])
rightRangeCount = subtractArrays(counts[d], counts[c])
if a > rd:
rightRangeCount = subtractArrays(
rightRangeCount, subtractArrays(counts[min(a, rc)], counts[rd]))
if rc > b:
rightRangeCount = subtractArrays(
rightRangeCount, subtractArrays(counts[rc], counts[max(b, rd)]))
if c > rb:
leftRangeCount = subtractArrays(
leftRangeCount, subtractArrays(counts[min(c, ra)], counts[rb]))
if ra > d:
leftRangeCount = subtractArrays(
leftRangeCount, subtractArrays(counts[ra], counts[max(d, rb)]))
ans.append(min(leftRangeCount) >= 0
and min(rightRangeCount) >= 0
and leftRangeCount == rightRangeCount)
return ans
def _getMirroredDiffs(self, s: str) -> list[int]:
diffs = [0]
for i, j in zip(range(len(s)), reversed(range(len(s)))):
if i >= j:
break
diffs.append(diffs[-1] + (s[i] != s[j]))
return diffs
def _getCounts(self, s: str) -> list[list[int]]:
count = [0] * 26
counts = [count.copy()]
for c in s:
count[ord(c) - ord('a')] += 1
counts.append(count.copy())
return counts
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.