MDantas's blog

Palindrome Problem
By MDantas, 11 years ago, In English

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'"

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

It's a problem form NEERC 2012. Click here to see the problem review. (problem H "Hyperdrome")

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

O(alphabet * N * map) Solution

Idea: string is palindrome iff there is 0 or 1 characters that appears odd number of times

Let 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

→ Reply