Bedao Regular Contest 13 - DELCHAR
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
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)~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.