Trò chơi xếp chữ
Đề bài
Mô tả
Một trò chơi xếp chữ trên điện thoại, người chơi có một chuỗi ký tự . Mỗi lượt chơi được phép xóa một ký tự bất kỳ. Trò chơi kết thúc khi chuỗi còn lại là palindrome (đọc xuôi ngược như nhau). Ví dụ: chuỗi "aca" hoặc "racecar" là chuỗi palindrome.
Yêu cầu: Tìm số lượt chơi ít nhất để chuỗi ban đầu trở thành palindrome.
Dữ liệu vào
Một dòng chứa chuỗi ký tự ( độ dài , chỉ gồm chữ cái tiếng Anh in thường).
Dữ liệu ra
In ra một số nguyên là số lượt chơi ít nhất.
Ràng buộc
- .
- chỉ gồm các chữ cái in thường từ a đến z.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| abcca | 1 | Xóa ký tự b, còn lại "acca". |
| abacda | 3 | Xóa ba ký tự b, c, d (hoặc b, a, d) để còn lại "aaa" (hoặc "aca"). Chuỗi palindrome dài nhất có thể giữ lại có độ dài . |
| racecar | 0 | Chuỗi đã là palindrome. |
| abcde | 4 | Các ký tự đều khác nhau, chỉ giữ lại được một ký tự. |
| ababa | 0 | Chuỗi đã là palindrome. |
| programming | 7 | Giữ lại "gmmg" (các ký tự g, m, m, g), xóa ký tự còn lại. |
Bình luận