### MDantas's blog

By MDantas, 7 years ago, ,

Does anyone knows how to solve this problem ?

"Given a string of size N ( 1 <= N <= 3 * 10^5 ), count how many pairs of positions (i,j) exists such that there's a way to form a palindromic string rearranging the characters from position 'i' to position 'j'"

• +1

 » 7 years ago, # | ← Rev. 2 →   +5 It's a problem form NEERC 2012. Click here to see the problem review. (problem H "Hyperdrome")
•  » » 7 years ago, # ^ |   0 Thank you.
 » 7 years ago, # | ← Rev. 2 →   +3 O(alphabet * N * map) Solution Idea: string is palindrome iff there is 0 or 1 characters that appears odd number of timesLet F(i) = bitmask. Every bit represent character. The bit for character x is set iff there is odd number of 'x' among first i characters.Let m = map from masks to integers. It represent how many times mask already seen.For evey character. Update F, for every possible character add m[F ^ this_caracter] to answer, add m[F] to answer, update m
•  » » 7 years ago, # ^ |   +3 Nice solution, thank you.