hardDynamic Programming 2DPure DSA~40 min
Fewest Insertions to Make a String a Palindrome
You may insert characters anywhere in a string. Find the minimum insertions so the whole string reads the same forwards and backwards.
Problem
Given a string s, return the minimum number of characters you must insert (at any positions) to make s a palindrome.
Input
A string s of lowercase English letters.
Output
An integer: the minimum number of insertions.
Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "leetcode"
Output
5
Five insertions, e.g. into \'leetcodocteel\', make it a palindrome.
Example 2
Input
s = "mbadm"
Output
2
"mbadm" → "mbdadbm" with two insertions.