# Palindrome Rearrangement Queries
**Difficulty:** HARD
[External](https://leetcode.com/problems/palindrome-rearrangement-queries)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-rearrangement-queries
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Naive Per-Query Calculation
This approach directly implements the logic for each query without any precomputation. For every query, it determines which parts of the string are fixed and which can be rearranged. It then checks if the fixed parts already satisfy the palindrome condition and if the rearrangeable parts have the necessary characters to form a palindrome.
**Time:** O(Q * N), where Q is the number of queries and N is the length of the string. For each query, we might iterate up to O(N) characters. · **Space:** O(1) or O(k) where k is the alphabet size (26). The space for frequency maps is constant and does not depend on the input size N.
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** The time complexity is proportional to the number of queries multiplied by the length of the string, which is too slow for the given constraints.; It performs a lot of redundant computations for overlapping query ranges.
### Explanation
For each query, we first identify the combined range of indices in the first half that are affected by the rearrangements. This range, let's call it `[L, R]`, is the union of the query's first interval `[a, b]` and the mapped second interval `[n-1-d, n-1-c]`. 

Any index `i` outside this `[L, R]` range is considered 'fixed'. For the string to be transformable into a palindrome, the characters at these fixed indices must already match their mirrored counterparts. That is, `s[i]` must equal `s[n-1-i]`. We can loop through the indices `0` to `L-1` and `R+1` to `n/2 - 1` to verify this.

For the 'rearrangeable' part corresponding to the index range `[L, R]`, a palindrome can be formed if and only if the collection of characters available in `s[L:R]` is the same as the collection of characters in its mirror image `s[n-1-R : n-1-L]`. We check this by building frequency counts for both substrings and ensuring they are identical.

```java
class Solution {
    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
        int n = s.length();
        int m = n / 2;
        boolean[] ans = new boolean[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int[] q = queries[i];
            int a = q[0], b = q[1], c = q[2], d = q[3];

            int cPrime = n - 1 - d;
            int dPrime = n - 1 - c;

            int l = Math.min(a, cPrime);
            int r = Math.max(b, dPrime);

            boolean possible = true;
            // Check fixed parts
            for (int j = 0; j < l; j++) {
                if (s.charAt(j) != s.charAt(n - 1 - j)) {
                    possible = false;
                    break;
                }
            }
            if (!possible) {
                ans[i] = false;
                continue;
            }
            for (int j = r + 1; j < m; j++) {
                if (s.charAt(j) != s.charAt(n - 1 - j)) {
                    possible = false;
                    break;
                }
            }
            if (!possible) {
                ans[i] = false;
                continue;
            }

            // Check rearrangeable part
            int[] counts1 = new int[26];
            int[] counts2 = new int[26];
            for (int j = l; j <= r; j++) {
                counts1[s.charAt(j) - 'a']++;
                counts2[s.charAt(n - 1 - j) - 'a']++;
            }

            for (int j = 0; j < 26; j++) {
                if (counts1[j] != counts2[j]) {
                    possible = false;
                    break;
                }
            }
            ans[i] = possible;
        }
        return ans;
    }
}
```
### Algorithm
- For each query `[a, b, c, d]`, we first determine the parts of the string that are affected by the rearrangements and the parts that are not.
- A character `s[i]` in the first half (`0 <= i < n/2`) can be changed if `i` is in the range `[a, b]`. A character `s[j]` in the second half (`n/2 <= j < n`) can be changed if `j` is in `[c, d]`. The character `s[j]` corresponds to `s[n-1-j]` in the first half. So, the range `[c, d]` in the second half corresponds to the range `[n-1-d, n-1-c]` in the first half.
- Let `I_left = [a, b]` and `I_right_mapped = [n-1-d, n-1-c]`. The union of these intervals, `[L, R] = [min(a, n-1-d), max(b, n-1-c)]`, represents the full range of indices in the first half that are involved in any rearrangement.
- **Fixed Parts Check:** For any index `i` outside of `[L, R]`, neither `s[i]` nor its mirror character `s[n-1-i]` can be changed. Therefore, for the string to become a palindrome, it must already be the case that `s[i] == s[n-1-i]` for all `i` in `[0, L-1]` and `[R+1, n/2 - 1]`. We iterate through these ranges and check this condition.
- **Rearrangeable Part Check:** For indices `i` within `[L, R]`, we can rearrange characters. For this part to be made palindromic, the multiset of characters in `s[L:R]` must be identical to the multiset of characters in its mirror part, `s[n-1-R : n-1-L]`. We can verify this by computing the frequency map (e.g., an array of size 26) for both substrings and comparing them.
- If both checks pass, the query result is `true`; otherwise, it's `false`.

## Prefix Sum Optimization
The naive approach is inefficient because it re-calculates information for each query. We can optimize this by pre-calculating prefix sums. This allows us to answer range queries about mismatches and character frequencies in constant time. The overall approach involves a one-time preprocessing step that takes linear time, followed by processing each query in constant time.
**Time:** O(N * k + Q * k), where N is the string length, Q is the number of queries, and k is the alphabet size. Since k is a constant (26), this simplifies to O(N + Q). · **Space:** O(N * k), where N is the string length and k is the alphabet size. This is dominated by the prefix sum arrays for character counts.
**Pros:** Extremely efficient for a large number of queries.; The time complexity is optimal for the given constraints.
**Cons:** Requires more space to store the prefix sum arrays.; The implementation is more complex than the naive approach.
### Explanation
This approach is based on the same core logic as the naive solution but uses prefix sums to speed up the checks for each query.

**Preprocessing:**
1.  **Mismatch Prefix Sums:** We create an array `mismatchPrefix` of size `n/2 + 1`. `mismatchPrefix[i+1]` stores the total number of mismatches (`s[j] != s[n-1-j]`) for `j` from `0` to `i`. This allows us to find the number of mismatches in any range `[x, y]` in O(1) by calculating `mismatchPrefix[y+1] - mismatchPrefix[x]`.
2.  **Character Frequency Prefix Sums:** We create two 2D arrays, `h1PrefixCounts` and `h2RevPrefixCounts`, of size `(n/2 + 1) x 26`. `h1PrefixCounts[i+1][k]` stores the frequency of character `k` in the prefix `s[0...i]`. Similarly, `h2RevPrefixCounts[i+1][k]` stores the frequency of character `k` in the prefix of the *reversed* second half, i.e., `s[n-1], s[n-2], ..., s[n-1-i]`. This allows us to find the character counts for any subsegment of the first half and its mirror in O(26) = O(1) time.

**Query Answering:**
With these precomputed structures, each query can be answered very quickly. We determine the `L` and `R` boundaries as before. The check for fixed parts becomes a simple lookup in the `mismatchPrefix` array. The check for the rearrangeable part involves using the two frequency prefix sum arrays to find the character counts for the range `[L, R]` and comparing them, which takes constant time (proportional to alphabet size).

```java
class Solution {
    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
        int n = s.length();
        int m = n / 2;

        // Precomputation
        // 1. Mismatch prefix sum
        int[] mismatchPrefix = new int[m + 1];
        for (int i = 0; i < m; i++) {
            mismatchPrefix[i + 1] = mismatchPrefix[i] + (s.charAt(i) == s.charAt(n - 1 - i) ? 0 : 1);
        }

        // 2. Character count prefix sums for both halves
        int[][] h1PrefixCounts = new int[m + 1][26];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 26; j++) {
                h1PrefixCounts[i + 1][j] = h1PrefixCounts[i][j];
            }
            h1PrefixCounts[i + 1][s.charAt(i) - 'a']++;
        }

        int[][] h2RevPrefixCounts = new int[m + 1][26];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 26; j++) {
                h2RevPrefixCounts[i + 1][j] = h2RevPrefixCounts[i][j];
            }
            h2RevPrefixCounts[i + 1][s.charAt(n - 1 - i) - 'a']++;
        }

        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] q = queries[i];
            int a = q[0], b = q[1], c = q[2], d = q[3];

            int cPrime = n - 1 - d;
            int dPrime = n - 1 - c;

            int l = Math.min(a, cPrime);
            int r = Math.max(b, dPrime);

            // Check fixed parts using prefix sums
            int mismatchesBefore = mismatchPrefix[l];
            int mismatchesAfter = mismatchPrefix[m] - mismatchPrefix[r + 1];
            if (mismatchesBefore > 0 || mismatchesAfter > 0) {
                ans[i] = false;
                continue;
            }

            // Check rearrangeable part using prefix sums
            boolean possible = true;
            for (int j = 0; j < 26; j++) {
                int count1 = h1PrefixCounts[r + 1][j] - h1PrefixCounts[l][j];
                int count2 = h2RevPrefixCounts[r + 1][j] - h2RevPrefixCounts[l][j];
                if (count1 != count2) {
                    possible = false;
                    break;
                }
            }
            ans[i] = possible;
        }

        return ans;
    }
}
```
### Algorithm
- **Preprocessing Step (O(N)):**
  - Create a prefix sum array `mismatchPrefix` for the first half of the string. `mismatchPrefix[i]` will store the number of indices `j < i` where `s[j] != s[n-1-j]`.
  - Create a 2D prefix sum array `h1PrefixCounts`. `h1PrefixCounts[i][char]` will store the count of `char` in the substring `s[0...i-1]`.
  - Create another 2D prefix sum array `h2RevPrefixCounts`. `h2RevPrefixCounts[i][char]` will store the count of `char` in the reversed second half's prefix of length `i` (i.e., from `s[n-1]` down to `s[n-i]`).
- **Query Processing Step (O(1) per query):**
  - For each query `[a, b, c, d]`, calculate `L` and `R` as in the naive approach.
  - **Fixed Parts Check:** Use the `mismatchPrefix` array to find the number of mismatches in `[0, L-1]` and `[R+1, n/2 - 1]` in O(1) time. If the count is greater than 0 for either range, the answer is `false`.
  - **Rearrangeable Part Check:** Use the character count prefix sum arrays (`h1PrefixCounts` and `h2RevPrefixCounts`) to get the frequency maps for `s[L:R]` and its mirror `s[n-1-R : n-1-L]` in O(1) time per character. Compare these counts for all 26 characters. If they don't match, the answer is `false`.
  - If both checks pass, the answer is `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean[] canMakePalindromeQueries(String s, int[][] queries) {
    int n = s.length();
    int m = n / 2;
    String t = new StringBuilder(s.substring(m)).reverse().toString();
    s = s.substring(0, m);
    int[][] pre1 = new int[m + 1][0];
    int[][] pre2 = new int[m + 1][0];
    int[] diff = new int[m + 1];
    pre1[0] = new int[26];
    pre2[0] = new int[26];
    for (int i = 1; i <= m; ++i) {
      pre1[i] = pre1[i - 1].clone();
      pre2[i] = pre2[i - 1].clone();
      ++pre1[i][s.charAt(i - 1) - 'a'];
      ++pre2[i][t.charAt(i - 1) - 'a'];
      diff[i] = diff[i - 1] + (s.charAt(i - 1) == t.charAt(i - 1) ? 0 : 1);
    }
    boolean[] ans = new boolean[queries.length];
    for (int i = 0; i < queries.length; ++i) {
      int[] q = queries[i];
      int a = q[0], b = q[1];
      int c = n - 1 - q[3], d = n - 1 - q[2];
      ans[i] = a <= c ? check(pre1, pre2, diff, a, b, c, d)
                      : check(pre2, pre1, diff, c, d, a, b);
    }
    return ans;
  }
private
  boolean check(int[][] pre1, int[][] pre2, int[] diff, int a, int b, int c,
                int d) {
    if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {
      return false;
    }
    if (d <= b) {
      return Arrays.equals(count(pre1, a, b), count(pre2, a, b));
    }
    if (b < c) {
      return diff[c] - diff[b + 1] == 0 &&
             Arrays.equals(count(pre1, a, b), count(pre2, a, b)) &&
             Arrays.equals(count(pre1, c, d), count(pre2, c, d));
    }
    int[] cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
    int[] cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));
    return cnt1 != null && cnt2 != null && Arrays.equals(cnt1, cnt2);
  }
private
  int[] count(int[][] pre, int i, int j) {
    int[] cnt = new int[26];
    for (int k = 0; k < 26; ++k) {
      cnt[k] = pre[j + 1][k] - pre[i][k];
    }
    return cnt;
  }
private
  int[] sub(int[] cnt1, int[] cnt2) {
    int[] cnt = new int[26];
    for (int i = 0; i < 26; ++i) {
      cnt[i] = cnt1[i] - cnt2[i];
      if (cnt[i] < 0) {
        return null;
      }
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<bool> canMakePalindromeQueries(string s,
                                        vector<vector<int>> &queries) {
    int n = s.length();
    int m = n / 2;
    string t = string(s.begin() + m, s.end());
    reverse(t.begin(), t.end());
    s = string(s.begin(), s.begin() + m);
    vector<vector<int>> pre1(m + 1, vector<int>(26));
    vector<vector<int>> pre2(m + 1, vector<int>(26));
    vector<int> diff(m + 1, 0);
    for (int i = 1; i <= m; ++i) {
      pre1[i] = pre1[i - 1];
      pre2[i] = pre2[i - 1];
      ++pre1[i][s[i - 1] - 'a'];
      ++pre2[i][t[i - 1] - 'a'];
      diff[i] = diff[i - 1] + (s[i - 1] == t[i - 1] ? 0 : 1);
    }
    vector<bool> ans(queries.size(), false);
    for (int i = 0; i < queries.size(); ++i) {
      vector<int> q = queries[i];
      int a = q[0], b = q[1];
      int c = n - 1 - q[3], d = n - 1 - q[2];
      ans[i] = (a <= c) ? check(pre1, pre2, diff, a, b, c, d)
                        : check(pre2, pre1, diff, c, d, a, b);
    }
    return ans;
  }

private:
  bool check(const vector<vector<int>> &pre1, const vector<vector<int>> &pre2,
             const vector<int> &diff, int a, int b, int c, int d) {
    if (diff[a] > 0 || diff[diff.size() - 1] - diff[max(b, d) + 1] > 0) {
      return false;
    }
    if (d <= b) {
      return count(pre1, a, b) == count(pre2, a, b);
    }
    if (b < c) {
      return diff[c] - diff[b + 1] == 0 &&
             count(pre1, a, b) == count(pre2, a, b) &&
             count(pre1, c, d) == count(pre2, c, d);
    }
    vector<int> cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
    vector<int> cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));
    return cnt1 != vector<int>() && cnt2 != vector<int>() && cnt1 == cnt2;
  }
  vector<int> count(const vector<vector<int>> &pre, int i, int j) {
    vector<int> cnt(26);
    for (int k = 0; k < 26; ++k) {
      cnt[k] = pre[j + 1][k] - pre[i][k];
    }
    return cnt;
  }
  vector<int> sub(const vector<int> &cnt1, const vector<int> &cnt2) {
    vector<int> cnt(26);
    for (int i = 0; i < 26; ++i) {
      cnt[i] = cnt1[i] - cnt2[i];
      if (cnt[i] < 0) {
        return vector<int>();
      }
    }
    return cnt;
  }
};

```

### Python

```python
class Solution:
    def canMakePalindromeQueries(self, s: str, queries: List[List[int]]) -> List[bool]: def count(pre: List[List[int]], i: int, j: int) -> List[int]: return [x - y for x, y in zip(pre[j + 1], pre[i])] def sub(cnt1: List[int], cnt2: List[int]) -> List[int]: res = [] for x, y in zip(cnt1, cnt2): if x - y < 0: return [] res . append(x - y) return res def check(pre1: List[List[int]], pre2: List[List[int]], a: int, b: int, c: int, d: int) -> bool: if diff[a] > 0 or diff[m] - diff[max(b, d) + 1] > 0: return False if d <= b: return count(pre1, a, b) == count(pre2, a, b) if b < c: return (diff[c] - diff[b + 1] == 0 and count(pre1, a, b) == count(pre2, a, b) and count(pre1, c, d) == count(pre2, c, d)) cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1)) cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d)) return bool(cnt1) and bool(cnt2) and cnt1 == cnt2 n = len(s) m = n // 2 t = s[m:][:: - 1] s = s[: m] pre1 = [[0] * 26 for _ in range(m + 1)] pre2 = [[0] * 26 for _ in range(m + 1)] diff = [0] * (m + 1) for i, (c1, c2) in enumerate(zip(s, t), 1): pre1[i] = pre1[i - 1][:] pre2[i] = pre2[i - 1][:] pre1[i][ord(c1) - ord("a")] += 1 pre2[i][ord(c2) - ord("a")] += 1 diff[i] = diff[i - 1] + int(c1 != c2) ans = [] for a, b, c, d in queries: c, d = n - 1 - d, n - 1 - c ok = (check(pre1, pre2, a, b, c, d) if a <= c else check(pre2, pre1, c, d, a, b)) ans . append(ok) return ans

```