Algorithms
Hard
2983
3203
Palindrome Rearrangement Queries
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.
"""
class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        
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.


Please complete the code below to solve above prblem:
```python
class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
        
```

my_solution = Solution()

test_input = { "s": "abcabc", "queries": [[1,1,3,5],[0,2,5,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "abbcdecbba", "queries": [[0,2,7,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "acbcab", "queries": [[1,2,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "bcdbdc", "queries": [[1,2,3,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "bb", "queries": [[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "eoquueqo", "queries": [[3,3,6,6]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "dd", "queries": [[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "ceddceddcc", "queries": [[0,1,6,8]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "bdbd", "queries": [[0,0,2,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "eeee", "queries": [[0,1,2,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "deebdeeddb", "queries": [[1,2,5,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "xwaswsxwaw", "queries": [[1,3,5,6]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "askloakosala", "queries": [[2,4,7,10]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "bbccbb", "queries": [[0,1,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "djaypzjpyzad", "queries": [[0,3,7,8]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "ajvnbnznjnzbva", "queries": [[5,6,10,11]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "vbeptwzvtwpzbe", "queries": [[3,6,10,11]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "cababc", "queries": [[1,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "cbbbbc", "queries": [[1,1,5,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "qupzexxhqxpzhxeu", "queries": [[2,4,8,12]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "cdbdbc", "queries": [[1,2,3,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "odaxusaweuasuoeudxwa", "queries": [[0,5,10,14]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "ujfscqolkwjucoswlkfq", "queries": [[1,9,17,18]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "ceacea", "queries": [[0,2,3,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "bnjzcgmnecxxbmnjngxzecxc", "queries": [[8,9,19,22]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "daeaed", "queries": [[0,2,3,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "ddaadd", "queries": [[0,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "ddedde", "queries": [[0,2,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "pmzwetzhzursuhmeswpzrztz", "queries": [[4,6,16,17]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "qcryjkdzmqyoojzrckymdqyq", "queries": [[2,8,21,22]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "qdltkndnclarncadtqnlldkr", "queries": [[3,4,15,16]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "ecbbce", "queries": [[0,1,3,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "eczecz", "queries": [[0,0,3,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "etuouqokbalafokfbuqaaoetlu", "queries": [[3,11,21,23]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "mpepem", "queries": [[0,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "nbpechkpmudbsenphdmsbbupck", "queries": [[6,7,18,19]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "bccacacb", "queries": [[3,3,4,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "stgjtzqwgkuadjgqugkwdtzast", "queries": [[5,10,13,23]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "qiyikbayvhkcgxyaqckgxkhivbyi", "queries": [[5,12,17,24]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "ceedceed", "queries": [[0,1,4,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "rcguwczbjhjhgqrggqcbwjzhjuch", "queries": [[5,7,16,20]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "ckwbnmqmtzbixrrkixbtbqzmnwmc", "queries": [[1,9,15,24]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True]

test_input = { "s": "riirxzxuqpspoiixpirsoxrzpiuq", "queries": [[1,6,14,21]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "geettndnusqufidtqdfgtsieenundu", "queries": [[6,8,19,23]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False]

test_input = { "s": "bb", "queries": [[0,0,1,1],[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "cc", "queries": [[0,0,1,1],[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "dd", "queries": [[0,0,1,1],[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "ee", "queries": [[0,0,1,1],[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "aeae", "queries": [[1,1,2,3],[1,1,3,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,False]

test_input = { "s": "eaae", "queries": [[0,1,3,3],[0,0,2,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "eded", "queries": [[0,1,2,3],[1,1,2,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "lrlr", "queries": [[0,1,2,3],[0,0,2,2]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,False]

test_input = { "s": "dbaabd", "queries": [[0,1,5,5],[1,2,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "dcbcbd", "queries": [[0,1,4,4],[0,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True]

test_input = { "s": "hykkyh", "queries": [[0,0,3,4],[1,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "lvrvrl", "queries": [[2,2,4,5],[0,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True]

test_input = { "s": "adceaecd", "queries": [[3,3,5,5],[0,1,4,6]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True]

test_input = { "s": "baadadba", "queries": [[1,2,4,5],[0,2,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True]

test_input = { "s": "bceaabec", "queries": [[1,3,4,7],[0,2,6,6]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "ifchcifh", "queries": [[1,2,5,6],[1,1,4,6]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "adeeeeeaed", "queries": [[2,4,7,9],[3,4,8,8]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,False]

test_input = { "s": "aedbdbddea", "queries": [[4,4,7,8],[2,2,8,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "caeaaaaaec", "queries": [[0,2,5,8],[0,0,5,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True]

test_input = { "s": "dbaccccdba", "queries": [[4,4,6,7],[2,3,8,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "deabadabea", "queries": [[0,3,7,9],[0,2,5,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True]

test_input = { "s": "eddeededee", "queries": [[0,3,6,9],[0,0,6,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "eedbbedebb", "queries": [[2,2,6,7],[2,2,5,6]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "gvtkakgvat", "queries": [[1,2,7,7],[2,3,7,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "bzvvicviczbv", "queries": [[1,2,7,8],[1,4,7,8]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "ljccjajcljac", "queries": [[2,4,6,10],[3,5,7,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "rxvzvezvrvxe", "queries": [[1,4,8,10],[3,3,10,11]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "amgpelwpmlaewg", "queries": [[3,4,7,9],[0,6,7,10]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True]

test_input = { "s": "leubdglmbglleudm", "queries": [[1,3,9,14],[2,6,13,14]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "ooxuznriuzrooixn", "queries": [[1,3,10,12],[1,4,9,13]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "nlaonaphinpnalohai", "queries": [[2,5,13,13],[2,7,9,14]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "rujokutobuttlysjusrtltuobkoytu", "queries": [[5,6,18,23],[10,13,15,26]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False]

test_input = { "s": "bb", "queries": [[0,0,1,1],[0,0,1,1],[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "cc", "queries": [[0,0,1,1],[0,0,1,1],[0,0,1,1]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "dbdb", "queries": [[0,0,2,2],[1,1,3,3],[0,1,2,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,True]

test_input = { "s": "ebbe", "queries": [[0,1,3,3],[1,1,2,2],[0,0,2,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "acacaa", "queries": [[0,1,5,5],[1,1,4,4],[1,2,3,4]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,True]

test_input = { "s": "bbaabb", "queries": [[0,1,4,5],[0,2,3,5],[2,2,5,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "bbebbe", "queries": [[0,1,3,5],[2,2,4,5],[0,1,5,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,False,False]

test_input = { "s": "ddaadd", "queries": [[1,1,4,4],[0,0,4,4],[0,2,3,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "nlhhln", "queries": [[2,2,4,5],[1,2,5,5],[2,2,3,3]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "zbebez", "queries": [[0,2,5,5],[1,1,3,5],[0,2,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "cbcbbcbc", "queries": [[0,2,7,7],[1,2,4,7],[0,2,4,5]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,True]

test_input = { "s": "deceecde", "queries": [[3,3,6,7],[1,2,4,5],[2,3,7,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,False,False]

test_input = { "s": "fydyfyyd", "queries": [[0,2,4,6],[1,3,4,7],[2,3,6,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [True,True,False]

test_input = { "s": "dccabcdbca", "queries": [[1,3,5,8],[2,4,7,7],[0,2,6,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "eacbdeacbd", "queries": [[4,4,8,9],[3,4,7,9],[0,0,6,8]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "eddaaedada", "queries": [[0,1,7,8],[0,1,7,8],[0,3,7,9]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "vvsbgsvgbv", "queries": [[0,1,6,9],[2,3,8,9],[0,0,6,7]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "sukesivksseuiv", "queries": [[2,3,11,13],[5,5,7,13],[2,5,8,13]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,True,False]

test_input = { "s": "pbcjpsfxwtbcfjwpsptx", "queries": [[0,4,13,13],[5,5,15,18],[2,3,13,18]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "natvhtruvwyutyvvnarhwt", "queries": [[5,7,14,21],[0,8,11,19],[2,8,11,14]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "yjsjywxbriejyxieysrwbj", "queries": [[4,5,15,19],[1,9,12,17],[3,6,12,18]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "ellaghdbmazdallhmegabddz", "queries": [[4,6,13,19],[4,11,17,17],[7,10,13,16]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "wcfnhuaulqxbuuxafcwhnbql", "queries": [[5,11,13,18],[7,8,18,21],[3,6,21,23]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]

test_input = { "s": "qyioinjmvpgpropimvqiygrnjp", "queries": [[1,4,15,25],[1,8,19,22],[4,9,18,23]] }
assert my_solution.canMakePalindromeQueries(**test_input) == [False,False,False]