Minimum Cost to Make a Palindrome

You are given a string \( S \) consisting only of lowercase English letters. Your task is to determine the minimum cost required to convert \( S \) into a palindrome.

A palindrome is a word that reads the same forward and backward. In order to achieve a palindromic string, you are allowed to perform the following operations any number of times:

• Insert any character at any position in the string with a cost of 1.
• Remove any character from the string with a cost of 1.

The goal is to compute the minimum total cost required so that the resulting string is a valid palindrome.

Formally, let \( dp[i][j] \) denote the minimum cost to convert the substring \( S[i \ldots j] \) into a palindrome. The recurrence is given by:

[ \begin{aligned} if ; S[i] == S[j]: \quad & dp[i][j] = dp[i+1][j-1] \[6pt] else: \quad & dp[i][j] = 1 + \min(dp[i+1][j],; dp[i][j-1]) \end{aligned} ]

Note: For a string of length \( n \), the answer is \( dp[0][n-1] \), with the base case that any empty string or single character is already a palindrome (i.e., cost 0).

Example:

Input:  abca
Output: 1

In the above example, inserting or deleting one character makes the string a palindrome.

inputFormat

The input is provided via stdin as a single line string \( S \) consisting only of lowercase English letters. The length of \( S \) does not exceed 10³.

outputFormat

Output the minimum cost (an integer) required to convert the string into a palindrome. The output should be printed to stdout.

## sample

abca

1