Skip to main content
Talentd

Palindrome Rearrangement Queries - Solution & Explanation

HardHash TableStringPrefix Sum33 min read
Practice this problem

Problem Statement

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.

Approach Overview

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 1: Frequency Count and Comparison

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: HashMap for Frequency Tracking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * 26).

Space Complexity: O(1) due to constant space for frequency arrays.

Try this approach in the editor →

Approach 3: Prefix Sum + Case Discussion

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:

  1. The prefix sum array pre_1 of string s, where pre_1[i][j] represents the quantity of character j in the first i characters of string s;
  2. The prefix sum array pre_2 of string t, where pre_2[i][j] represents the quantity of character j in the first i characters of string t;
  3. The difference array 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:

  1. The prefix substrings 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;
  2. If 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;
  3. If 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.
  4. If 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Count with Prefix ArraysO(n + q * 26)O(n * 26)Best for large strings and many queries; constant-time substring frequency checks
HashMap Frequency TrackingO(n + q * k)O(k)Simpler implementation; suitable when query ranges are small

Video Solution

2983. Palindrome Rearrangement Queries | Weekly Leetcode 378 • codingMohan • 1,597 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Palindrome Rearrangement Queries easy or hard?
Palindrome Rearrangement Queries is categorized as Hard because it combines multiple concepts: palindrome feasibility rules, substring frequency tracking, and efficient handling of many queries. The challenge lies in designing a preprocessing strategy that avoids recomputing counts repeatedly.
Palindrome Rearrangement Queries Python/Java solution
Python and Java implementations typically build a 2D prefix array where each index stores counts for 26 characters. Queries extract frequency differences and check if the counts satisfy palindrome constraints. This approach keeps each query extremely fast.
How to solve Palindrome Rearrangement Queries in O(n)?
Use prefix sums to store cumulative character frequencies. For each query, retrieve counts for the affected ranges in O(1) and check if the resulting character counts can form a palindrome. Because the alphabet size is constant, the verification step is effectively constant time.
What is the best approach for Palindrome Rearrangement Queries?
The most efficient approach uses prefix frequency arrays with parity checks. Precompute cumulative counts for all characters, then compare frequencies of mirrored ranges during each query. This reduces query processing to constant time per character set, giving an overall complexity of O(n + q * 26).
Is Palindrome Rearrangement Queries asked at Google/Amazon/Meta?
Problems combining prefix sums, substring queries, and palindrome validation appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test knowledge of string manipulation, frequency counting, and query optimization techniques.
What data structure is used in Palindrome Rearrangement Queries?
The core data structures include prefix frequency arrays and hash tables. Prefix arrays allow constant-time substring frequency retrieval, while hash maps can track character counts dynamically during queries.
What is the time complexity of Palindrome Rearrangement Queries?
Using prefix frequency counts, preprocessing takes O(n * 26) and each query takes O(26) time because only the alphabet frequencies need comparison. The total complexity becomes O(n + q). A simpler HashMap-based method may take O(k) per query depending on substring length.

Ready to solve this problem?

Practice Palindrome Rearrangement Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Chunked Palindrome Decomposition