XÂU CON

Nguồn: Đề thi chọn đội tuyển Tin học tỉnh Khánh Hòa ngày 04/04/2017

Cho một xâu ký tự S gồm N ký tự thường trong bảng chữ cái tiếng Anh và một số nguyên dương K.

Yêu cầu: Bạn hãy tìm một chuỗi con liên tục dài nhất sao cho chuỗi con đó có chứa đúng K ký tự khác nhau.

Dữ liệu vào: Tệp văn bản SUBSTRING.INP gồm:

+ Dòng đầu ghi hai số nguyên N và K.

+ Dòng thứ hai gồm N ký tự chữ cái in thường trong bảng chữ cái tiếng Anh.

Kết quả: Ghi ra tệp văn bản SUBSTRING.OUT một số nguyên duy nhất là độ dài chuỗi con liên tục dài nhất tìm được.

Ví dụ:

SUBSTRING.INP	SUBSTRING.OUT
7 2 abbabef	5

Trong ví dụ trên, chuỗi dài nhất tìm được gồm 5 ký tự đầu là “abbab”, chỉ gồm 2 ký tự khác nhau là ‘a’ và ‘b’.

Giới hạn dữ liệu

+ 0 < K ≤ min(N , 26).

+ Có 60% số tests với 0 < N ≤ 2000.

+ Có 40% tests còn lại với 2000 < N ≤ 200000.

 Test - code - solution - đề (word)