Question
Enchanted Mirror of Words
In the Kingdom of Letters, there is a magical mirror that only reflects words that are palindromes — words that read the same forwards and backwards.
A young scribe finds an old scroll with a string of letters s. To unlock the mirror’s magic, the scribe can insert letters anywhere in the string, one at a time, to make it a palindrome.
Your task is to help the scribe find the minimum number of insertions needed to turn the string into a palindrome.
Input
The first and only line of the input contains the string s.
Output
Print an integer representing the minimum number of insertions required to convert the string s into a palindrome.
Example
Input:
mbadm
Output:
2
Explanation:
The string can be converted to "mbdadbm" or "mdbabdm".
mbadm
Output:
2
Explanation:
The string can be converted to "mbdadbm" or "mdbabdm".