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.
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 mspl-between is 0. And all mspl's for each index is 1. If two characters are equal, we increment the previous characters mspl to mspl-between+2. We check the global max each time. mspl-between is then updated to the previous value of the mspl of that previous index, we save it too in case it gets changed.
Resolves: #221
Algorithm:
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.
We can solve this problem using dynamic programming. Notice the sort of recursiveness here: the maximum palindromic subsequence length (
mpsl) at some indexican be the maximum mspl starting at some indexj. Or, if characters at these indices are equal, 2+mspl starting at some indexk, 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 mspl-between is 0. And all mspl's for each index is 1. If two characters are equal, we increment the previous characters mspl to mspl-between+2. We check the global max each time. mspl-between is then updated to the previous value of the mspl of that previous index, we save it too in case it gets changed.