Nén chuỗi theo khối lặp liên tiếp
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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$
Community Discussion