Bedao Mini Contest 11 - BEAUTYSTR

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

~Copium~ rất mê cái đẹp, anh ta không những mê gái mà còn mê cả xâu. Một xâu ~Copium~ cho là đẹp nếu nó tồn tại một cách sắp xếp sao cho xâu đó là một palindrome. Một hôm một người bạn của anh ta đưa cho anh một xâu ~S~, và với tính tò mò của mình, ~Copium~ đã dành hàng tiếng để đếm số xâu con ~[l, r]~ ~(1 \le l \le r \le n)~ của xâu ~S~ sao cho nó là một xâu đẹp. Nhưng vì xâu ~S~ quá dài nên ~Copium~ đang cần bạn giúp!

Một xâu palindrome được định nghĩa là xâu khi đọc từ trái sang phải và ngược lại đều có kết quả như nhau.

Input

  • Dòng đầu gồm một số nguyên ~n~ là chiều dài của xâu ~S~ ~(1 \le n \le 10^5)~
  • Dòng thứ hai là xâu ~S~ có chiều dài ~n~ chỉ gồm các ký tự từ ~[a, z]~ viết thường và các số thuộc ~[0, 9]~

Output

  • In ra một số duy nhất là số xâu con đẹp trong xâu ~S~.

Sample Input 1

5
abacc

Sample Output 1

9

Sample Input 2

5
bedao

Sample Output 2

5

Subtask

  • ~10\%~ số test thoả mãn xâu ~S~ chỉ gồm ~2~ ký tự 'a''b'
  • ~30\%~ số test tiếp theo có ~n \le 2 \times 10^3~
  • ~60\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.



  • -11
    Khanhchan   commented on Aug. 3, 2022, 2:37 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.