Minimum Insertion Steps for Palindrome Problem

Minimum Insertion Steps for Palindrome Problem — ExecCode Hard DSA Practice

Solve the Minimum Insertion Steps for Palindrome problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Given a string s, return the minimum number of characters that must be inserted anywhere to make it a palindrome. This can be solved with interval DP, or by computing the longest palindromic subsequence. If the longest palindromic subsequence has length L, then the answer is len(s) - L.

Examples

Input mbadm; Output 2. Input leetcode; Output 5

Constraints

1 <= len(s) <= 500 s contains lowercase English letters.

Practice Minimum Insertion Steps for Palindrome free on ExecCode. Browse DSA problems, topic map, and placement guides.