Nén chuỗi theo khối lặp liên tiếp

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một xâu $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh viết thường (a đến z) và một số nguyên $K$. Bạn được phép thực hiện tối đa $K$ thao tác; mỗi thao tác cho phép thay đổi một ký tự bất kỳ trong $S$ thành một chữ cái viết thường khác.

Hãy tìm độ dài lớn nhất của một đoạn con liên tiếp trong $S$ chỉ gồm các ký tự giống hệt nhau sau khi thực hiện tối đa $K$ thao tác.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le N \le 10^5$, $0 \le K \le N$).
  • Dòng thứ hai chứa xâu $S$ có độ dài $N$.
Dữ liệu ra
  • In ra một số nguyên duy nhất là độ dài lớn nhất tìm được.
Ví dụ
Input Output
6 1
abacba
3
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le K \le N$
Draft saved