P8638 [Lanqiao Cup 2016 NOI Qualifier A] Password Shedding

Archaeologists on Planet X discovered a batch of ancient passwords. These passwords are sequences made by threading together seeds of four types of plants: A, B, C, and D. After careful analysis, they found that these password strings should originally have been symmetric from front to back (that is, palindromic strings). Because of the long passage of time, many seeds have fallen off, so the strings may have lost their mirror-like property. Your task is: Given the password string you see now, compute the minimum number of seeds that must have fallen off from its original state for it to possibly become what it is now.

Input one line, which is the password string seen now. (Its length does not exceed $1000$.)

Output a positive integer, indicating the minimum number of seeds that have fallen off.

Lanqiao Cup 2016 provincial contest, Group A, Problem I. Translated by ChatGPT 5