Nhóm Chuỗi Con Đảo Chữ
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Cho chuỗi $S$ có độ dài $N$ và một số nguyên $K$. Hai chuỗi con có độ dài $K$ được gọi là "đảo chữ" (anagram) của nhau nếu chúng chứa cùng tập ký tự với cùng số lần xuất hiện.
Hãy đếm số nhóm đảo chữ phân biệt của các chuỗi con có độ dài $K$ trong $S$. Mỗi nhóm bao gồm tất cả các chuỗi con có độ dài $K$ là đảo chữ của nhau.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
- Dòng thứ hai chứa chuỗi $S$ có độ dài $N$.
Dữ liệu ra
- In ra một số nguyên — số nhóm đảo chữ phân biệt.
Ví dụ
| Input | Output |
|---|---|
| 7 3\nabcbacb | 3 |
| 4 2\nabab | 2 |
Giới hạn
- $1 \le K \le N \le 10^5$
- Chuỗi chỉ chứa ký tự in thường từ
ađếnz.
Giải thích ví dụ 1: Chuỗi con độ dài 3: abc, bcb, cba, bac, acb. Nhóm 1: {abc, cba, bac, acb} (đảo chữ). Nhóm 2: {bcb}. Nhóm 3 không có thêm. Tổng 2 nhóm... Xem lại: abc→sorted=abc, bcb→sorted=bbc, cba→sorted=abc, bac→sorted=abc, acb→sorted=abc. Vậy có 2 nhóm.
Community Discussion