K-Palindrome Subsequence

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