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:
s[ai:bi], where 0 <= ai <= bi < n / 2.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.
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 <= 1051 <= queries.length <= 105queries[i].length == 4ai == queries[i][0], bi == queries[i][1]ci == queries[i][2], di == queries[i][3]0 <= ai <= bi < n / 2n / 2 <= ci <= di < n n is even.s consists of only lowercase English letters.Problem Overview: You are given a string and multiple queries that allow rearranging characters within specific ranges. For each query, determine whether the resulting string can still form a palindrome. The key requirement is checking whether character frequencies across mirrored positions can be balanced after rearrangement.
Approach 1: Frequency Count and Comparison (O(n + q * 26) time, O(n * 26) space)
This approach relies on prefix frequency arrays to track how many times each character appears up to every index. Using prefix sums, you can compute the character distribution of any substring in constant time. For each query, extract the frequency counts of the affected ranges and compare them with their mirrored segments. A string can be rearranged into a palindrome if every character count can be paired except possibly one center character. Because the alphabet size is fixed (26 lowercase letters), checking balance takes O(26) time per query.
The insight: palindrome feasibility depends only on frequency parity. By storing cumulative counts, you avoid rebuilding frequency arrays repeatedly. This method fits well when the string length and query count are large, because preprocessing happens once and each query becomes a small constant-time check.
Approach 2: HashMap for Frequency Tracking (O(n + q * k) time, O(k) space)
This method uses a hash table to track character frequencies inside the segments affected by each query. For every query, iterate through the selected substring ranges, update counts in a map, and verify whether characters can be paired symmetrically. The palindrome condition is checked by counting how many characters have odd frequency.
The advantage is implementation simplicity. You avoid maintaining a large prefix matrix and directly compute counts from the relevant characters. However, the per‑query cost grows with the substring size k, making it slower when queries span large sections of the string. This approach works well for smaller inputs or when queries affect short ranges.
Both approaches depend on understanding character parity in palindromes. If two mirrored halves contain identical frequency distributions after allowed rearrangements, the string can form a valid palindrome.
Recommended for interviews: The prefix frequency technique using string preprocessing and prefix sums is the expected solution. It demonstrates awareness of query optimization patterns. A brute or direct HashMap counting approach shows understanding of the palindrome condition, but the prefix-based solution shows stronger algorithmic design for handling large numbers of queries efficiently.
This approach involves counting the frequency of characters in each of the given substrings for a query and checking if they can form a palindrome.
If two halves can independently be rearranged into the same set of characters, then the entire string can be rearranged into a palindrome.
This C solution defines a helper function canFormPalindrome that counts character frequencies within two specified substrings using arrays of size 26 (for each alphabet letter). It then compares the two frequency counts to determine if they are anagrams (rearrangements that can form palindromes).
The main function, canMakePalindrome, processes each query and stores the result of the canFormPalindrome function in an output array, which it returns.
Time Complexity: O(m * 26) for m queries where each involves counting and comparing character frequencies; considered O(m) as 26 is a constant.
Space Complexity: O(1), since the space used for frequency counts does not scale with input size.
In this method, use HashMaps (or similar data structures) to track character frequency instead of fixed-size arrays, which can be more versatile.
Ensure that the mappings in both substrings are equal if they can form a palindrome.
This C solution utilizes dynamic memory for the character counts, accommodating variable string lengths more explicitly.
It processes each query in a way similar to fixed arrays, but dynamic allocation may suit situations where we cannot establish fixed-size character sets.
Time Complexity: O(m * 26).
Space Complexity: O(1) due to constant space for frequency arrays.
Let's denote the length of string s as n, then half of the length is m = \frac{n}{2}. Next, we divide string s into two equal-length segments, where the second segment is reversed to get string t, and the first segment remains as s. For each query [a_i, b_i, c_i, d_i], where c_i and d_i need to be transformed to n - 1 - d_i and n - 1 - c_i. The problem is transformed into: for each query [a_i, b_i, c_i, d_i], determine whether s[a_i, b_i] and t[c_i, d_i] can be rearranged to make strings s and t equal.
We preprocess the following information:
pre_1 of string s, where pre_1[i][j] represents the quantity of character j in the first i characters of string s;pre_2 of string t, where pre_2[i][j] represents the quantity of character j in the first i characters of string t;diff of strings s and t, where diff[i] represents the quantity of different characters in the first i characters of strings s and t.For each query [a_i, b_i, c_i, d_i], let's assume a_i \le c_i, then we need to discuss the following cases:
s[..a_i-1] and t[..a_i-1] of strings s and t must be equal, and the suffix substrings s[max(b_i, d_i)+1..] and t[max(b_i, d_i)..] must also be equal, otherwise, it is impossible to rearrange to make strings s and t equal;d_i \le b_i, it means the interval [a_i, b_i] contains the interval [c_i, d_i]. If the substrings s[a_i, b_i] and t[a_i, b_i] contain the same quantity of characters, then it is possible to rearrange to make strings s and t equal, otherwise, it is impossible;b_i < c_i, it means the intervals [a_i, b_i] and [c_i, d_i] do not intersect. Then the substrings s[b_i+1, c_i-1] and t[b_i+1, c_i-1] must be equal, and the substrings s[a_i, b_i] and t[a_i, b_i] must be equal, and the substrings s[c_i, d_i] and t[c_i, d_i] must be equal, otherwise, it is impossible to rearrange to make strings s and t equal.c_i \le b_i < d_i, it means the intervals [a_i, b_i] and [c_i, d_i] intersect. Then the characters contained in s[a_i, b_i], minus the characters contained in t[a_i, c_i-1], must be equal to the characters contained in t[c_i, d_i], minus the characters contained in s[b_i+1, d_i], otherwise, it is impossible to rearrange to make strings s and t equal.Based on the above analysis, we iterate through each query [a_i, b_i, c_i, d_i], and determine whether it satisfies the above conditions.
The time complexity is O((n + q) times |\Sigma|), and the space complexity is O(n times |\Sigma|). Where n and q are the lengths of string s and the query array queries respectively; and |\Sigma| is the size of the character set. In this problem, the character set is lowercase English letters, so |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Frequency Count and Comparison | Time Complexity: O(m * 26) for m queries where each involves counting and comparing character frequencies; considered O(m) as 26 is a constant. Space Complexity: O(1), since the space used for frequency counts does not scale with input size. |
| HashMap for Frequency Tracking | Time Complexity: O(m * 26). Space Complexity: O(1) due to constant space for frequency arrays. |
| Prefix Sum + Case Discussion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count with Prefix Arrays | O(n + q * 26) | O(n * 26) | Best for large strings and many queries; constant-time substring frequency checks |
| HashMap Frequency Tracking | O(n + q * k) | O(k) | Simpler implementation; suitable when query ranges are small |
2983. Palindrome Rearrangement Queries | Weekly Leetcode 378 • codingMohan • 1,580 views views
Watch 4 more video solutions →Practice Palindrome Rearrangement Queries with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor