Minimum Insertions to Form a Palindrome

Given a string s consisting of lowercase English letters, your task is to determine the minimum number of insertions needed to convert s into a palindrome.

A palindrome is a string that reads the same backward as forward. The problem can be approached by finding the Longest Palindromic Subsequence (LPS) of the given string. The minimum number of insertions required is given by:

$$\text{insertions} = |s| - \text{LPS}(s)$$

where \(|s|\) denotes the length of the string s, and \(\text{LPS}(s)\) is the length of the longest palindromic subsequence in s.

inputFormat

The input is read from standard input. It contains a single line with a non-empty string s of lowercase English letters.

outputFormat

Output the minimum number of insertions required to transform the given string into a palindrome. The result should be printed to standard output.

race

3