Bedao Regular Contest 13 - DELCHAR

View as PDF
Submit solution
Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho xâu ~s~ gồm các kí tự in thường trong bảng chữ cái tiếng Anh. Gọi ~t_i~ là xâu nhận được từ việc xóa kí tự thứ ~i~ trong xâu ~s~.

Hãy đếm số cặp số ~(i, j)~ thỏa mãn ~i < j~ và ~t_i = t_j~.

Input

  • Dòng đầu tiên gồm số nguyên dương ~n~ (~2 \le n \le 3 \times 10^5~) — độ dài của xâu ~s~.

  • Dòng tiếp theo chứa xâu ~s~ có độ dài ~n~, gồm các kí tự in thường trong bảng chữ cái tiếng Anh.

Output

  • In ra một dòng duy nhất là đáp án của bài toán: số cặp số ~(i, j)~ thỏa mãn ~i < j~ và ~t_i = t_j~.

Sample Input 1

6
bccaaa

Sample Output 1

4

Notes

Ở test ví dụ trên, ta có:

  • ~t_1 =~ ccaaa

  • ~t_2 =~ bcaaa

  • ~t_3 =~ bcaaa

  • ~t_4 =~ bccaa

  • ~t_5 =~ bccaa

  • ~t_6 =~ bccaa

Vì vậy, có ~4~ cặp số ~(i, j)~ thỏa mãn yêu cầu đề bài là ~(2, 3)~, ~(4, 5)~, ~(4, 6)~ và ~(5, 6)~.

Comments

Please read the guidelines before commenting.


  • -21
    Yangcoi  commented on Feb. 9, 2023, 2:08 a.m.

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


    • -5
      fpccvn  commented on Oct. 16, 2023, 8:27 a.m.

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