2983. Palindrome Rearrangement Queries Hard

1/**
2 * [2983] Palindrome Rearrangement Queries
3 *
4 * You are given a 0-indexed string s having an even length n.
5 * You are also given a 0-indexed 2D integer array, queries, where queries[i] = [ai, bi, ci, di].
6 * For each query i, you are allowed to perform the following operations:
7 * 
8 * 	Rearrange the characters within the substring s[ai:bi], where 0 <= ai <= bi < n / 2.
9 * 	Rearrange the characters within the substring s[ci:di], where n / 2 <= ci <= di < n.
10 * 
11 * For each query, your task is to determine whether it is possible to make s a palindrome by performing the operations.
12 * Each query is answered independently of the others.
13 * 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 i^th query, and false otherwise.
14 * 
15 * 	A substring is a contiguous sequence of characters within a string.
16 * 	s[x:y] represents the substring consisting of characters from the index x to index y in s, both inclusive.
17 * 
18 *  
19 * <strong class="example">Example 1:
20 * 
21 * Input: s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]
22 * Output: [true,true]
23 * Explanation: In this example, there are two queries:
24 * In the first query:
25 * - a0 = 1, b0 = 1, c0 = 3, d0 = 5.
26 * - So, you are allowed to rearrange s[1:1] => a<u>b</u>cabc and s[3:5] => abc<u>abc</u>.
27 * - To make s a palindrome, s[3:5] can be rearranged to become => abc<u>cba</u>.
28 * - Now, s is a palindrome. So, answer[0] = true.
29 * In the second query:
30 * - a1 = 0, b1 = 2, c1 = 5, d1 = 5.
31 * - So, you are allowed to rearrange s[0:2] => <u>abc</u>abc and s[5:5] => abcab<u>c</u>.
32 * - To make s a palindrome, s[0:2] can be rearranged to become => <u>cba</u>abc.
33 * - Now, s is a palindrome. So, answer[1] = true.
34 * 
35 * <strong class="example">Example 2:
36 * 
37 * Input: s = "abbcdecbba", queries = [[0,2,7,9]]
38 * Output: [false]
39 * Explanation: In this example, there is only one query.
40 * a0 = 0, b0 = 2, c0 = 7, d0 = 9.
41 * So, you are allowed to rearrange s[0:2] => <u>abb</u>cdecbba and s[7:9] => abbcdec<u>bba</u>.
42 * It is not possible to make s a palindrome by rearranging these substrings because s[3:6] is not a palindrome.
43 * So, answer[0] = false.
44 * <strong class="example">Example 3:
45 * 
46 * Input: s = "acbcab", queries = [[1,2,4,5]]
47 * Output: [true]
48 * Explanation: In this example, there is only one query.
49 * a0 = 1, b0 = 2, c0 = 4, d0 = 5.
50 * So, you are allowed to rearrange s[1:2] => a<u>cb</u>cab and s[4:5] => acbc<u>ab</u>.
51 * To make s a palindrome s[1:2] can be rearranged to become a<u>bc</u>cab.
52 * Then, s[4:5] can be rearranged to become abcc<u>ba</u>.
53 * Now, s is a palindrome. So, answer[0] = true.
54 *  
55 * Constraints:
56 * 
57 * 	2 <= n == s.length <= 10^5
58 * 	1 <= queries.length <= 10^5
59 * 	queries[i].length == 4
60 * 	ai == queries[i][0], bi == queries[i][1]
61 * 	ci == queries[i][2], di == queries[i][3]
62 * 	0 <= ai <= bi < n / 2
63 * 	n / 2 <= ci <= di < n 
64 * 	n is even.
65 * 	s consists of only lowercase English letters.
66 * 
67 */
68pub struct Solution {}
69
70// problem: https://leetcode.com/problems/palindrome-rearrangement-queries/
71// discuss: https://leetcode.com/problems/palindrome-rearrangement-queries/discuss/?currentPage=1&orderBy=most_votes&query=
72
73// submission codes start here
74
75impl Solution {
76    pub fn can_make_palindrome_queries(s: String, queries: Vec<Vec<i32>>) -> Vec<bool> {
77        
78    }
79}
80
81// submission codes end
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn test_2983() {
89    }
90}
91