P1435 [IOI 2000] Palindromic String

IOI 2000 Problem 1.

A palindrome is a symmetric string. For any given string, by inserting some characters, it can be turned into a palindrome. The task is to find the minimum number of characters that need to be inserted to make the given string a palindrome. For example, $\verb!Ab3bd!$ can become a palindrome after inserting $2$ characters, such as $\verb!dAb3bAd!$ or $\verb!Adb3bdA!$, but it cannot become a palindrome with fewer than $2$ insertions. Note: This problem is case-sensitive.

The input consists of one line containing a string.

Output a single integer: the minimum number of inserted characters.

### Constraints Let the length of the string be $l$. For all testdata, $0 < l \le 1000$. Translated by ChatGPT 5