Watch 5 video solutions for Palindrome Rearrangement Queries, a hard level problem involving Hash Table, String, Prefix Sum. This walkthrough by codingMohan has 1,580 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |