Informatica Online Judge

  Hyperdrome [2273 / 08E1]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 10   Total Tried : 2


The Champion of this Problem (C++) : gs16109 - ms / 497byte
My Best Submission (C++) : N/A

[NEERC 2012 H번 "Hyperdrome"]

Background

민제는 동현이에게 길이 N짜리 문자열을 선물로 주었다.

동현이는 너무나 감동한 나머지 다음과 같이 말했다.

"어머, 이 길이 N짜리 문자열에는 섞어서 팰린드롬을 만들 수 있는 부분문자열이 무려 K개나 있잖아! 이건 내가 예전부터 꼭 갖고 싶었던 문자열이야!"

이때, K를 구하여라.

Input

첫째 줄에는 문자열의 길이 N(1 <= N <= 300000)이 주어진다.
둘째 줄에는 동현이가 선물로 받은 문자열이 주어진다. 문자열은 알파벳 대소문자로 구성되어 있다.

Output

원래 문자열의 부분문자열 중, 섞어서 팰린드롬을 만들 수 있는 것의 개수를 출력한다. 부분문자열이 같더라도 등장하는 위치가 다르면 서로 다른 것으로 센다.
섞어서 팰린드롬을 만들 수 있는 문자열이란, 문자들을 적절히 재배열해서 팰린드롬을 만들 수 있는 문자열을 의미한다.

IO Example

입력 예제 1

3
aaa

출력 예제 1

6


입력 예제 2

3
aAA

출력 예제 2

5

예제 2에서 부분문자열은 a, A, A, aA, AA, aAA로 총 6개가 있고, 이 중 섞어서 팰린드롬을 만들 수 있는 것은 a, A, A, AA, aAA의 5개이다.
"aAA"의 경우 그 자체로는 팰린드롬이 아니지만, AaA로 재배열하면 팰린드롬이 된다는 점에 유의하라.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]