Minimum Insertions to Palindrome

You are given a string s of length \(n\) (where \(1 \le n \le 5000\)) consisting of only lowercase English letters. Your task is to determine the minimum number of single-character insertions required to make the string a palindrome.

A palindrome is a string that reads the same forwards and backwards.

Example:

• For s = "abca", the answer is 1.
• For s = "race", the answer is 3.
• For s = "aabb", the answer is 2.

Use dynamic programming to solve this problem efficiently.

inputFormat

The input consists of a single line containing the string s.

You should read the input from standard input (stdin).

outputFormat

Output a single integer, the minimum number of single-character insertions required to convert s into a palindrome. Write the output to standard output (stdout).

abca

1