Блог пользователя MDantas

Palindrome Problem
Автор MDantas, 11 лет назад, По-английски

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
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить