VM 09 Bài 01 - Palindrome String

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon 2009 - Warm up Round
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một xâu ký tự, bạn có thể biến đổi xâu này theo cách sau: Chọn một loại ký tự, biến đổi tất cả các ký tự loại này trong xâu thành một loại ký tự khác. Chi phí của một phép biến đổi như vậy bằng số lượng ký tự đã bị thay đổi. Bạn được phép áp dụng các phép biến đổi nhiều lần, chi phí của nhiều phép biến đổi bằng tổng chi phí của từng phép biến đổi.

Ví dụ, nếu bạn có xâu ~acaabc~, sau khi biến tất cả các ký tự ~c~ thành ~b~, bạn có xâu ~abaabb~, bạn mất một lượng chi phí là ~2~ cho phép biến đổi này do có ~2~ ký tự ~c~ bị thay đổi.

Yêu cầu: Tìm chi phí nhỏ nhất để biến đổi một xâu trở thành xâu đối xứng .

Input

  • Một dòng duy nhất ghi xâu ban đầu.

Output

  • Một số duy nhất thể hiện chi phí tối ưu.

Giới hạn

  • Độ dài xâu không vượt quá ~10^{5}~ .
  • Mỗi ký tự trong xâu là chữ cái hoặc chữ số.
  • Trong ~50\%~ số test, độ dài xâu không vượt quá ~100~.

Sample Input

acaabc

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.