#5157. PALINFIX - Xâu Đối Xứng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Một xâu được gọi là đối xứng (palindrome) nếu đọc từ trái sang phải giống hệt như đọc từ phải sang trái. Cho một xâu ký tự S chỉ bao gồm các chữ cái Latin in thường. Bạn hãy cho biết cần thay đổi (không thêm, bớt) ít nhất bao nhiêu ký tự để xâu S trở thành một xâu đối xứng.

Dữ liệu: Một dòng duy nhất chứa xâu ký tự S . Độ dài của S không vượt quá 10^5 .

Kết quả: Một số nguyên duy nhất là số lượng ký tự tối thiểu cần thay đổi.

Ví dụ:

Dữ liệu:

racecar

Kết quả:

0

Giải thích: Xâu racecar vốn đã là xâu đối xứng.

Ví dụ 2:

Dữ liệu:

google

Kết quả:

3

Giải thích: Ta thay 3 ký tự thành elggle

Giới hạn:

  • 1 \le \text{độ dài}(S) \le 10^5 .