Minimum Insertions to Form a Palindrome

A palindrome is a string that reads the same forwards and backwards. Given any string, by inserting a number of characters, it is always possible to transform it into a palindrome. The task is to determine the minimum number of characters that need to be inserted into the given string so that it becomes a palindrome.

For example, for the string Ab3bd, by inserting 2 characters, it can be transformed into the palindrome dAb3bAd or Adb3bdA. Inserting fewer than 2 characters will not suffice.

Note: This problem is case-sensitive.

The mathematical formulation using LaTeX is as follows: Let s be the input string and LPS(s) be the length of the longest palindromic subsequence of s. The minimum number of insertions required is given by:

inputFormat

The input consists of a single string s on a single line, which represents the string to be transformed into a palindrome.

Constraints:

• The string may contain letters, digits, and symbols.
• The comparison is case-sensitive.

outputFormat

Output a single integer representing the minimum number of characters that need to be inserted into the string s so that it becomes a palindrome.

sample

Ab3bd

2