You're given a string S consisting of N lowercase English characters. A string is considered good if it can be rearranged to form a palindrome.
There are Q Queries, Each query contains two integers, l and r, representing a range within the string S. For each query, determine the number of good substrings within the inclusive range [l, r].
How can we solve this problem ? The issue im facing is that if [l, r] can be shuffled to be a palindrome, [l + 1, r] not necessarily can be shuffled. Hence not able to precompute some answers.
Mo
A palindrome is possible if all characters appear an even number of times, or there is exactly one character that appears an odd number of times.
In other words, we only care about the parity of the frequency of the characters to determine if a substring can be shuffled to be a palindrome.
The frequency array $$$\mod 2$$$ can be seen as a bitmask ($$$26$$$ bits) where the ith bit($$$0$$$-indexed) represents the parity of the frequency of the ith letter. It doesn't exceed $$$2^{26}-1$$$
Eg: the information for aaabbc will be $$$00000...101$$$ (read from right to left)
Let's store the bitmask for all prefixes of s in a $$$\text{pref}[]$$$ array ($$$1$$$-indexed, pref[0]=0)
Using prefix xor logic, bitmask for $$$\text{s}[i...j] = \text{pref}[j] \oplus \text{pref}[i-1]$$$
From the conditions for a palindrome, either bitmask is $$$0$$$ or there is exactly $$$1$$$ bit set in the bitmask. There are just $$$27$$$ target bitmasks that represent palindromes.
The problem is now reduced to finding all pairs $$$i,j (l-1 \leq i<j \leq r)$$$ such that $$$\text{pref}[i] \oplus \text{pref}[j]$$$ is one of the target numbers for each query. This is standard with Mo's algorithm. Setting block size to 300 worked fast enough.
My code here
The code looks so small and cool :D