Given a string *S* of length *n* and a positive integer *k*, design an O(*nk*)-time algorithm to determine whether it is possible to delete *k* characters from *S*, so that the resulting string is a palindrome.

**Solution**:

A simple solution is to find the longest palindromic subsequence of *S* and test whether its length is at least *n* – *k*. Finding the longest palindromic subsequence is reduced to finding the longest common subsequence between *S* and its reverse, *S*‘, and this takes O() time. However, we don’t need to find the longest common subsequence. We only need to determine whether the longest common subsequence has a length at least *n* – *k*. Since the length of *S* and the *S*‘ are the same, this problem is identical to determine whether the edit distance between *S* and *S*‘ is at most *k*. When use dynamic programming technique to solve edit distance problem, we can prune some branches that have edit distance at least *k*. The complexity will be O(*nk*).

**解法**：

一個簡單的解法是找出*S*的最長回文子序列，然後判斷其長度。計算最長回文子序列等價於找出S和S的逆字串*S*‘的最長共同子序列，但是這需要花O()的時間。但是我們不需要找出最長共同子序列，只需要判斷是否存在有一共同子序列其長度至少為*n* – *k*。 因為*S*和*S*‘等長，這問題等價於判斷*S*和*S*‘的edit distance是否不大於*k*。當使用動態規劃技巧時，我們可以直接把edit distance至少為*k*的分支刪除，時間複雜度為O(*nk*)。

Reference: Careercup