Chuỗi đa dạng (Diverse String)

Nguồn: Sở Giáo dục và Đào tạo Hà Nội — Đề chính thức kỳ thi chọn học sinh giỏi thành phố và chọn đội tuyển học sinh giỏi dự thi Olympic quốc gia các môn văn hóa, lớp 12 THPT, năm học 2026–2027 (Bảng A)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một chuỗi ký tự $S$ chỉ chứa những ký tự thường trong bảng chữ cái tiếng Anh và hai số nguyên dương $K, X$.

Một chuỗi ký tự được gọi là chuỗi đa dạng nếu tồn tại ít nhất $K$ ký tự khác nhau mà mỗi ký tự trong số đó xuất hiện ít nhất $X$ lần trong chuỗi.

Có thể thực hiện thao tác đổi một ký tự trong $S$ thành một ký tự bất kỳ khác.

Hãy xác định độ dài chuỗi con liên tiếp ngắn nhất của $S$ sao cho chuỗi con đó là một chuỗi đa dạng sau tối đa một thao tác đổi.

Input

• Dòng đầu tiên chứa hai số nguyên dương $K, X$.
• Dòng thứ hai chứa chuỗi ký tự $S$ chỉ gồm các chữ cái thường tiếng Anh.

Output

In ra một số nguyên là độ dài chuỗi con liên tiếp ngắn nhất thỏa mãn yêu cầu. Nếu không tồn tại chuỗi con thỏa mãn thì in ra -1.

Subtask

• Subtask 1 (60 điểm): $1\le K\le 26$, $1\le X\le 10^5$, $|S|\le 100$.
• Subtask 2 (20 điểm): $1\le K\le 26$, $1\le X\le 10^5$, $|S|\le 1000$.
• Subtask 3 (20 điểm): $1\le K\le 26$, $1\le X\le 10^5$, $|S|\le 10^5$; không có ràng buộc thêm.

Ví dụ 1

Input

2 3
abcacbabac

Output

6

Giải thích

Chọn chuỗi con acbaba có độ dài $6$. Đổi ký tự c thành b thu được chuỗi abbaba. Khi đó hai ký tự a và b đều xuất hiện $3$ lần, nên chuỗi thu được là chuỗi đa dạng.

Ví dụ 2

Input

2 2
abcde

Output

-1

Giải thích

Không thể chọn được một chuỗi con mà sau tối đa một thao tác đổi có ít nhất $2$ ký tự khác nhau, mỗi ký tự xuất hiện ít nhất $2$ lần.