Xâu con k-đều
Đề bài
Mô tả
Cho xâu gồm các chữ cái tiếng Anh in hoa. Với một số nguyên dương , một xâu con -đều của là một xâu con gồm ký tự liên tiếp của mà tất cả đều là cùng một chữ cái. Hai xâu con -đều được coi là khác nhau nếu chúng bắt đầu ở hai vị trí khác nhau. Ví dụ, xâu AAAB có hai xâu con -đều (cả hai đều là AA, bắt đầu ở vị trí và ) và một xâu con -đều.
Bạn được phép đổi nhiều nhất một ký tự của thành một chữ cái tiếng Anh in hoa bất kỳ. Với mỗi , hãy tìm số lượng xâu con -đều nhỏ nhất có thể của sau khi đổi. Lưu ý rằng cách đổi được chọn độc lập cho từng .
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
Mỗi bộ dữ liệu gồm một dòng duy nhất chứa xâu () gồm các chữ cái tiếng Anh in hoa.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng gồm số nguyên. Số nguyên thứ là số lượng xâu con -đều nhỏ nhất có thể của sau khi đổi nhiều nhất một ký tự.
Ràng buộc
- .
- ; chỉ gồm các chữ cái tiếng Anh in hoa.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 Z AAB |
1 3 0 0 |
Bộ thứ nhất: dù đổi thế nào, xâu một ký tự luôn có đúng một xâu con -đều. Bộ thứ hai: mỗi ký tự luôn là một xâu con -đều nên với đáp án là ; đổi ký tự giữa thành C được ACB, không còn xâu con -đều hay -đều nào. |
| 2 AAAAA ABBBBA |
5 2 0 0 0 6 1 0 0 0 0 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: đổi ký tự giữa được AABAA, còn hai xâu con -đều (AA ở đầu và ở cuối) và không còn xâu con -đều nào. Bộ thứ hai: đổi thành ABBCBA còn một xâu con -đều (BB); xâu này cũng không còn xâu con -đều nào. |
Bình luận