# 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 nk. Finding the longest palindromic subsequence is reduced to finding the longest common subsequence between S and its reverse, S‘, and this takes O($n^2$) 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 nk. 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).

Reference: Careercup