Minimum Insertions to Make a String Palindrome

Given a string s, return the minimum number of insertions needed to make s a palindrome. Insertions can be made at any position. Pattern focus: Longest palindromic subsequence. The answer is derived from the LPS length.

Input Format

s = input string

Output Format

minimum number of insertions

Constraints

  • 0 <= s.length <= 1000
  • s contains lowercase English letters.

Examples

Example 1:

Input:

s = "zzazz"

Output:

0

Explanation:

The string is already a palindrome.

Example 2:

Input:

s = "mbadm"

Output:

2

Explanation:

Insertions can turn it into a palindrome such as madam.

Loading...
Minimum Insertions to Make a String Palindrome