LC: 1216. Valid Palindrome III - spiralgo/algorithms GitHub Wiki

1216. Valid Palindrome III:

The Essence:

Being able to remove some characters basically means that the palindrome does not have to be contiguous, a substring. It can thus be a subsequence. Our task is then to find the longest palindromic subsequence, and check if it's longer than the string size - k removed characters.

Details:

We can solve this problem using dynamic programming. Notice the sort of recursiveness here: the maximum palindromic subsequence length (mpsl) at some index i can be the maximum mspl starting at some index j. Or, if characters at these indices are equal, 2+mspl starting at some index k, i>k>j, mspl between i and j. It's the maximum of these two.

We can easily derive a dp procedure from this. We pick some index and look for all indices before it. Initially the mpsl-between is 0. And all mpsl's for each index is 1. If two characters are equal, we increment the previous characters mpsl to mspl-between+2. We check the global max each time. mpsl-between is then updated to the previous value of the mpsl of that previous index, we save it too in case it gets changed.

A detailed explanation and implementation is here: https://github.com/spiralgo/algorithms/pull/382