Palindrome Rearrangement Queries

Hard

#2662Time: 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.

Patterns

Prefix Sum

Data structures

Hash Table String

Prompt

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] = [a_i, b_i, c_i, d_i].

For each query i, you are allowed to perform the following operations:

Rearrange the characters within the substring s[a_i:b_i], where 0 <= a_i <= b_i < n / 2.
Rearrange the characters within the substring s[c_i:d_i], where n / 2 <= c_i <= d_i < 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 i^th 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 <= 10⁵
1 <= queries.length <= 10⁵
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 is even.
s consists of only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {3        int n = s.length();4        int m = n / 2;5        boolean[] ans = new boolean[queries.length];6 7        for (int i = 0; i < queries.length; i++) {8            int[] q = queries[i];9            int a = q[0], b = q[1], c = q[2], d = q[3];10 11            int cPrime = n - 1 - d;12            int dPrime = n - 1 - c;13 14            int l = Math.min(a, cPrime);15            int r = Math.max(b, dPrime);16 17            boolean possible = true;18            // Check fixed parts19            for (int j = 0; j < l; j++) {20                if (s.charAt(j) != s.charAt(n - 1 - j)) {21                    possible = false;22                    break;23                }24            }25            if (!possible) {26                ans[i] = false;27                continue;28            }29            for (int j = r + 1; j < m; j++) {30                if (s.charAt(j) != s.charAt(n - 1 - j)) {31                    possible = false;32                    break;33                }34            }35            if (!possible) {36                ans[i] = false;37                continue;38            }39 40            // Check rearrangeable part41            int[] counts1 = new int[26];42            int[] counts2 = new int[26];43            for (int j = l; j <= r; j++) {44                counts1[s.charAt(j) - 'a']++;45                counts2[s.charAt(n - 1 - j) - 'a']++;46            }47 48            for (int j = 0; j < 26; j++) {49                if (counts1[j] != counts2[j]) {50                    possible = false;51                    break;52                }53            }54            ans[i] = possible;55        }56        return ans;57    }58}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

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].
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).

1class Solution {2    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {3        int n = s.length();4        int m = n / 2;5 6        // Precomputation7        // 1. Mismatch prefix sum8        int[] mismatchPrefix = new int[m + 1];9        for (int i = 0; i < m; i++) {10            mismatchPrefix[i + 1] = mismatchPrefix[i] + (s.charAt(i) == s.charAt(n - 1 - i) ? 0 : 1);11        }12 13        // 2. Character count prefix sums for both halves14        int[][] h1PrefixCounts = new int[m + 1][26];15        for (int i = 0; i < m; i++) {16            for (int j = 0; j < 26; j++) {17                h1PrefixCounts[i + 1][j] = h1PrefixCounts[i][j];18            }19            h1PrefixCounts[i + 1][s.charAt(i) - 'a']++;20        }21 22        int[][] h2RevPrefixCounts = new int[m + 1][26];23        for (int i = 0; i < m; i++) {24            for (int j = 0; j < 26; j++) {25                h2RevPrefixCounts[i + 1][j] = h2RevPrefixCounts[i][j];26            }27            h2RevPrefixCounts[i + 1][s.charAt(n - 1 - i) - 'a']++;28        }29 30        boolean[] ans = new boolean[queries.length];31        for (int i = 0; i < queries.length; i++) {32            int[] q = queries[i];33            int a = q[0], b = q[1], c = q[2], d = q[3];34 35            int cPrime = n - 1 - d;36            int dPrime = n - 1 - c;37 38            int l = Math.min(a, cPrime);39            int r = Math.max(b, dPrime);40 41            // Check fixed parts using prefix sums42            int mismatchesBefore = mismatchPrefix[l];43            int mismatchesAfter = mismatchPrefix[m] - mismatchPrefix[r + 1];44            if (mismatchesBefore > 0 || mismatchesAfter > 0) {45                ans[i] = false;46                continue;47            }48 49            // Check rearrangeable part using prefix sums50            boolean possible = true;51            for (int j = 0; j < 26; j++) {52                int count1 = h1PrefixCounts[r + 1][j] - h1PrefixCounts[l][j];53                int count2 = h2RevPrefixCounts[r + 1][j] - h2RevPrefixCounts[l][j];54                if (count1 != count2) {55                    possible = false;56                    break;57                }58            }59            ans[i] = possible;60        }61 62        return ans;63    }64}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean[] canMakePalindromeQueries(String s, int[][] queries) {4    int n = s.length();5    int m = n / 2;6    String t = new StringBuilder(s.substring(m)).reverse().toString();7    s = s.substring(0, m);8    int[][] pre1 = new int[m + 1][0];9    int[][] pre2 = new int[m + 1][0];10    int[] diff = new int[m + 1];11    pre1[0] = new int[26];12    pre2[0] = new int[26];13    for (int i = 1; i <= m; ++i) {14      pre1[i] = pre1[i - 1].clone();15      pre2[i] = pre2[i - 1].clone();16      ++pre1[i][s.charAt(i - 1) - 'a'];17      ++pre2[i][t.charAt(i - 1) - 'a'];18      diff[i] = diff[i - 1] + (s.charAt(i - 1) == t.charAt(i - 1) ? 0 : 1);19    }20    boolean[] ans = new boolean[queries.length];21    for (int i = 0; i < queries.length; ++i) {22      int[] q = queries[i];23      int a = q[0], b = q[1];24      int c = n - 1 - q[3], d = n - 1 - q[2];25      ans[i] = a <= c ? check(pre1, pre2, diff, a, b, c, d)26                      : check(pre2, pre1, diff, c, d, a, b);27    }28    return ans;29  }30private31  boolean check(int[][] pre1, int[][] pre2, int[] diff, int a, int b, int c,32                int d) {33    if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {34      return false;35    }36    if (d <= b) {37      return Arrays.equals(count(pre1, a, b), count(pre2, a, b));38    }39    if (b < c) {40      return diff[c] - diff[b + 1] == 0 &&41             Arrays.equals(count(pre1, a, b), count(pre2, a, b)) &&42             Arrays.equals(count(pre1, c, d), count(pre2, c, d));43    }44    int[] cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));45    int[] cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));46    return cnt1 != null && cnt2 != null && Arrays.equals(cnt1, cnt2);47  }48private49  int[] count(int[][] pre, int i, int j) {50    int[] cnt = new int[26];51    for (int k = 0; k < 26; ++k) {52      cnt[k] = pre[j + 1][k] - pre[i][k];53    }54    return cnt;55  }56private57  int[] sub(int[] cnt1, int[] cnt2) {58    int[] cnt = new int[26];59    for (int i = 0; i < 26; ++i) {60      cnt[i] = cnt1[i] - cnt2[i];61      if (cnt[i] < 0) {62        return null;63      }64    }65    return cnt;66  }67}

1class Solution {2public:3  vector<bool> canMakePalindromeQueries(string s,4                                        vector<vector<int>> &queries) {5    int n = s.length();6    int m = n / 2;7    string t = string(s.begin() + m, s.end());8    reverse(t.begin(), t.end());9    s = string(s.begin(), s.begin() + m);10    vector<vector<int>> pre1(m + 1, vector<int>(26));11    vector<vector<int>> pre2(m + 1, vector<int>(26));12    vector<int> diff(m + 1, 0);13    for (int i = 1; i <= m; ++i) {14      pre1[i] = pre1[i - 1];15      pre2[i] = pre2[i - 1];16      ++pre1[i][s[i - 1] - 'a'];17      ++pre2[i][t[i - 1] - 'a'];18      diff[i] = diff[i - 1] + (s[i - 1] == t[i - 1] ? 0 : 1);19    }20    vector<bool> ans(queries.size(), false);21    for (int i = 0; i < queries.size(); ++i) {22      vector<int> q = queries[i];23      int a = q[0], b = q[1];24      int c = n - 1 - q[3], d = n - 1 - q[2];25      ans[i] = (a <= c) ? check(pre1, pre2, diff, a, b, c, d)26                        : check(pre2, pre1, diff, c, d, a, b);27    }28    return ans;29  }30 31private:32  bool check(const vector<vector<int>> &pre1, const vector<vector<int>> &pre2,33             const vector<int> &diff, int a, int b, int c, int d) {34    if (diff[a] > 0 || diff[diff.size() - 1] - diff[max(b, d) + 1] > 0) {35      return false;36    }37    if (d <= b) {38      return count(pre1, a, b) == count(pre2, a, b);39    }40    if (b < c) {41      return diff[c] - diff[b + 1] == 0 &&42             count(pre1, a, b) == count(pre2, a, b) &&43             count(pre1, c, d) == count(pre2, c, d);44    }45    vector<int> cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));46    vector<int> cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));47    return cnt1 != vector<int>() && cnt2 != vector<int>() && cnt1 == cnt2;48  }49  vector<int> count(const vector<vector<int>> &pre, int i, int j) {50    vector<int> cnt(26);51    for (int k = 0; k < 26; ++k) {52      cnt[k] = pre[j + 1][k] - pre[i][k];53    }54    return cnt;55  }56  vector<int> sub(const vector<int> &cnt1, const vector<int> &cnt2) {57    vector<int> cnt(26);58    for (int i = 0; i < 26; ++i) {59      cnt[i] = cnt1[i] - cnt2[i];60      if (cnt[i] < 0) {61        return vector<int>();62      }63    }64    return cnt;65  }66};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem