Hoán Đổi Kề Biến Xâu Thành Đối Xứng

Buổi 64 — Contest Chặng 7 greedy Strings
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một xâu ký tự $S$ có độ dài $N$ chỉ gồm các chữ cái tiếng Anh in thường ('a'..'z'). Ở mỗi thao tác, bạn được phép chọn hai ký tự đứng liền kề nhau trong $S$ và đổi chỗ chúng cho nhau.

Hãy tìm số thao tác ít nhất cần thực hiện để biến đổi $S$ thành một xâu đối xứng (palindrome — đọc xuôi và ngược đều giống nhau). Nếu không thể biến $S$ thành xâu đối xứng, hãy in ra -1.

Dữ liệu vào

Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 5000$).

Dữ liệu ra

In ra số thao tác hoán đổi kề tối thiểu, hoặc -1 nếu không thể thực hiện.

Ví dụ
Input Output
mamad 3
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved