Bài 5

Cho xâu $S$ chỉ chứa các kí tự chữ cái Tiếng Anh in thường (‘a’..‘z’). Gọi độ dài của xâu $S$ là số lượng kí tự của xâu $S$, kí hiệu là $N$ ($1 \le N \le 10^6$). Xâu con liên tiếp của xâu $S$ có dạng $S_i, S_{i+1}, S_{i+2}, \dots, S_j$ ($1 \le i \le j \le N$). Xâu con liên tiếp khác rỗng được gọi là xâu con đẹp nếu nó có đúng $K$ kí tự phân biệt khác nhau. Ví dụ: Xâu $S$ = “abc”, $K = 2$, xâu $S$ có các xâu con là “a”, “b”, “c”, “ab”, “bc”, “abc”. Chỉ có 2 xâu con “ab”, “bc” là xâu con đẹp vì chứa đúng 2 kí tự khác nhau.

Yêu cầu: Cho xâu $S$ và số nguyên dương $K$, đếm số lượng xâu con đẹp là xâu con của xâu $S$.

Nhập từ bàn phím trên 2 dòng:

• Dòng thứ nhất: chứa số nguyên dương $K$ ($1 \le K \le 26$; $1 \le K \le N \le 10^6$);
• Dòng thứ hai: chứa xâu $S$ có độ dài không quá $10^6$

Xuất ra màn hình một số nguyên dương duy nhất là số lượng xâu con đẹp của xâu $S$. Nếu không có xâu con nào thỏa mãn yêu cầu thì xuất ra số 0.

• Có 40% test ứng với 40% số điểm thỏa mãn $1 \le N \le 10^2$;
• Có 30% test ứng với 30% số điểm thỏa mãn $10^2 < N \le 10^3$;
• Có 30% test ứng với 30% số điểm thỏa mãn $10^3 < N \le 10^6$.