You are given a string S initially and some Q queries. For each query you will have 2 integers L and R. For each query, you have to perform the following operations:

Arrange the letters from L to R inclusive to make a Palindrome. If you can form many such palindromes, then take the one that is lexicographically minimum. Ignore the query if no palindrome is possible on rearranging the letters.

You have to find the final string after all the queries.


1 <= length(S) <= 10^5

1 <= Q <= 10^5

1<= L <= R <= length(S)

Sample Input :


mmcs 1

1 3

Sample Output:


Explanation: The initial string is mmcs, there is 1 query which asks to make a palindrome from 1 3, so the palindrome will be mcm. Therefore the string will mcms.

If each query takes O(N) time, the overall time complexity would be O(NQ) which will give TLE. So each query should take around O(logn) time. But I am not able to think of anything which will solve this question. I think since we only need to find the final string rather than what every query result into, I guess there must be some other way to approach this question. Can anybody help me?

I found this question in a sample test of a coding competition.


The key idea is that there are only $26$ alphabets in the string. Let $\Sigma$ denote the set of alphabets, i.e., $|\Sigma| = 26$. Assume that you have a data structure that for every pair of $L$ and $R$, computes the number of occurrences of any alphabet in $[L,R]$ efficiently. Using those numbers, you can easily check in $O(|\Sigma|)$ time if the substring from $L$ to $R$ forms a palindrome or not; this part is easy I leave the details to you. After finding the palindrome, you need to update the data structure without changing the original string; this part is complex, which I will explain in more detail.

Data Structure: Maintain an Interval tree (or segment tree) for each alphabet. A leaf in the tree corresponds to an interval $[s,t]$, such that the alphabet appears contiguously in the string $S$ from positions $s$ to $t$. For example: Suppose the string $S$ is $baaaedaabbbzz$ and the alphabet is $a$. Then the leaves of the segment tree of alphabet $a$ will be: $[2,4], [7,8]$ since $a$ appears in the string from positions $2$ to $4$, and it also appears in the string from positions $7$ to $8$. Similarly, for $b$, the leaves of its segment tree would be $[1,1], [9,11]$.

The segment trees for all the alphabets can be constructed in $O(|S| \log |S|)$ time. If you are not familiar with segment trees, you will need to study it by yourself.

Query: For a given query $[L,R]$, you can find the number of occurrences of any alphabet between positions $L$ and $R$ using the corresponding segment tree of the alphabet. This takes $O(\log |S|)$ time for each alphabet. Now, you can easily check if the sub-string makes a palindrome or not.

Updating the Data Structure: Now, you do not need to output/print the palindrome; you just need to find the interval in which an alphabet occurs in the palindrome (the lexicographically smallest one). This can be done in $O(|\Sigma|)$ time; it is easy, I leave the details to you. There will be at most two intervals for each alphabet in the palindrome. Update the segment trees of each alphabet by adding these new intervals. Adding these two intervals takes $O(\log |S|)$ time. However, you also need to remove some old intervals that overlap with these new intervals. It also takes $O(\log |S|)$ time: Why? Think in terms of amortized analysis.

Lastly, after performing all the queries, you can reconstruct the final string using the segment trees.

Overall running time is $O((|S|+|\Sigma|) \cdot \log |S|) \approx 10^7$.

  • $\begingroup$ It was very well explained. Thank you so much for the answer. $\endgroup$ Sep 19 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.