Minimum Insertions to Form a Palindrome

Given a string \( s \), determine the minimum number of character insertions required to convert \( s \) into a palindrome. A palindrome is a string that reads identically forwards and backwards (e.g. madam). This problem can be approached by finding the longest palindromic subsequence of \( s \) and then computing the difference \( n - LCS(s, s^R) \), where \( n \) is the length of \( s \) and \( s^R \) is the reverse of \( s \).

inputFormat

The input consists of a single line containing a string \( s \). The string contains only lowercase English letters.

outputFormat

Output a single integer representing the minimum number of insertions required to transform the given string into a palindrome.

ab

1