Độ đẹp của xâu
Xem PDFCho xâu \(S\) có độ dài \(n\) và một số nguyên \(k(1\le k\le n)\). Xâu \(S\) có "độ đẹp" là \(x\), nếu \(x\) là số nguyên không âm lớn nhất thỏa mãn:
-
Trong \(S\) tồn tại \(x\) xâu con (gồm những phần tử liên tiếp) có độ dài là \(k\) và chúng không được chồng lên nhau
-
Tất cả các phần tử của \(x\) xâu con này phải giống nhau.
Yêu cầu: Cho số nguyên \(k\) và xâu \(S\) có độ dài là \(n\). Tìm "độ đẹp" của \(S\)
Input
-
Dòng thứ nhất chứa hai số nguyên \(n\) và \(k(1\le k\le n\le 2.10^5)\)
-
Dòng thứ hai chứa xâu \(S\) có độ dài là \(n\)
Output
- In ra đáp án cần tìm
Example
Test 1
Input
4 2
aabbOutput
1Note
Ở ví dụ 1: Xâu \("aabb"\) có "độ đẹp" là \(1\) vì chỉ có tối đa \(1\) xâu con có độ dài là \(2\) mà tất cả các phần tử của chúng giống nhau!
Test 2
Input
7 2
aabbbaaOutput
2Note
Ở ví dụ 2: Xâu \("aabbbaaa"\) có độ đẹp là \(2\) vì có \(2\) xâu con \("aa"\) xuất hiện trong \("aabbbaa"\)
Bình luận
Bài này chúng ta sẽ sử dụng char để lưu string. Sử dụng vòng lặp for duyệt hết mảng char, xét kí tự thứ s[i] thì ta sẽ kiểm tra xem kí tự này có lặp đủ k lần không bằng cách tăng i lên. Nếu đủ, ta dùng 1 mảng đếm phân phối, và tăng giá trị ánh xạ của kí tự đó lên 1 đơn vị. Lưu ý ko sử dụng max để kiểm tra luôn x max, thay vào đó ta nên kiểm tra sau khi chạy hết ct.
-
5
VoBaThongL921
8:22 a.m. 28 Tháng 10, 2021
-
4
longkold00
8:29 a.m. 28 Tháng 10, 2021
2 bình luận nữaánh xạ là cái gì anh ;-;
nó giống kiểu key để truy cập tới giá trị á, giống như a['a'] chẳng hạn :V