Minimum Insertions to Form a Palindrome

Given a string s, determine the minimum number of insertions needed to make it a palindrome. A palindrome is a string that reads the same forwards and backwards. You are required to utilize dynamic programming techniques to solve this problem.

For example, the string "abc" can be converted to a palindrome by inserting 2 characters, e.g. transforming it to "abcba" or "acbca".

inputFormat

The input is provided via standard input (stdin) and consists of a single line containing the string s. The string only contains lowercase English letters with a length between 1 and 500.

outputFormat

Output a single integer via standard output (stdout), which represents the minimum number of insertions required to transform s into a palindrome.

abc

2