Intuition

At first glance, it seems like we need to decide where to insert characters to make the string a palindrome.

Instead of thinking about what to insert, think about what we can keep.

The characters that are already part of the Longest Palindromic Subsequence (LPS) do not need any insertion.

Only the remaining characters need to be inserted.