Thất bại muộn
Đề bài
Mô tả
Một xâu được gọi là xâu đối xứng (palindrome) nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau.
Để kiểm tra một xâu có đối xứng hay không, một lập trình viên dùng hàm C++ sau:
bool isPalindrome(string s) {
int low = 0;
int high = s.size() - 1;
while (low < high) {
if (s[low] != s[high])
return false;
++low;
--high;
}
return true;
}
Cho xâu gồm các chữ cái tiếng Anh in hoa. Bạn có thể sắp xếp lại các chữ cái của theo thứ tự bất kỳ (giữ nguyên thứ tự ban đầu cũng được) để thu được một xâu mới .
Bạn muốn isPalindrome(T) trả về false, nhưng đồng thời muốn hàm phát hiện ra điều đó muộn nhất có thể.
Hãy tìm số lần lặp lớn nhất của vòng lặp while có thể được thực hiện trước khi hàm trả về false. Lần lặp mà hàm trả về false cũng được tính, nên đây chính là số lần điều kiện s[low] != s[high] được kiểm tra. Nếu không có cách sắp xếp nào làm hàm trả về false, in ra .
Dữ liệu vào
Một dòng duy nhất chứa xâu (), chỉ gồm các chữ cái in hoa từ A đến Z.
Dữ liệu ra
In ra một số nguyên: số lần lặp lớn nhất như mô tả ở trên, hoặc nếu không có cách sắp xếp nào làm hàm trả về false.
Ràng buộc
- .
- chỉ gồm các chữ cái in hoa từ A đến Z.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| AABBCDEF | 3 | Có thể sắp xếp thành ABCDEFBA. Hai lần so sánh đầu đều gặp hai chữ giống nhau (A với A, rồi B với B). Ở lần so sánh thứ ba hàm gặp hai chữ khác nhau là C và F nên trả về false. Vòng lặp được thực hiện lần. |
| AAAAA | -1 | Mọi cách sắp xếp đều cho xâu AAAAA, là xâu đối xứng, nên hàm không bao giờ trả về false. |
| AABBCC | 2 | Ví dụ bổ sung (không có trong đề gốc). Sắp xếp thành ABCBCA: lần so sánh thứ nhất gặp A với A, lần thứ hai gặp B với C. Không thể đạt lần: khi đó hai cặp ngoài cùng phải giống nhau, và hai chữ còn lại ở giữa luôn là hai chữ giống nhau vì mỗi chữ cái xuất hiện một số chẵn lần. |
Bình luận