Minimum Insertions to Palindrome — Solution & Editorial

Back to the Problem

The answer is |S| minus the longest palindromic subsequence, computed by interval DP.

Complexity: O(|S|²)