A k-palindrome is a string which transforms into a palindrome on removing at most k characters from it. Given a string S, and an interger K, find whether S is a k-palindrome or not? Constraints: S has at most 20,000 characters and 0<=k<=30

It can be done O(n*k) time complexity. Basically we need to find if string S can be converted to it's reverse within 2*k insertion and deletion. Let me explain with an example. Say the string (S) is aabca. Then reverse (S') is acbaa. After atmost k deletion we want the string to be a palindrome i.e read same in backward direction i.e reverse. We can treat this as edit distance problem where only deletion and insertion are permitted. aabca -> (delete) abca -> (insert) acbca -> (delete) acba -> (insert) acbaa Note that, removing one character from string S actually translates to two operation here. So, we need to find out if S can be converted to S' within 2*k insertion deletion. Since, we are permitted only k deletion, while comparing character of S and S', we do not need to look beyond k character (both backward and forward). This can be done in O(n*k) time complexity. Space complexity is O(k).

Suraj explains the same idea I mentioned in my answer on CareerCup - http://www.careercup.com/question?id=6287528252407808 The question asks if we can transform the given string S into its reverse deleting at most K letters. We could modify the traditional Edit-Distance algorithm, considering only deletions, and check if this edit distance is <= K. There is a problem though. S can have length = 20,000 and the Edit-Distance algorithm takes O(N^2). Which is too slow. (From here on, I'll assume you're familiar with the Edit-Distance algorithm and its DP matrix) However, we can take advantage of K. We are only interested *if* manage to delete K letters. This means that any position more than K positions away from the main diagonal is useless because its edit distance must exceed those K deletions. Since we are comparing the string with its reverse, we will do at most K deletions and K insertions (to make them equal). Thus, we need to check if the ModifiedEditDistance is <= 2*K Here's the code: int ModifiedEditDistance(const string& a, const string& b, int k) { int i, j, n = a.size(); // sample for simplicity. we should use only a window of size // 2*k+1 or dp[2][MAX] and alternate rows. only need row i-1 int dp[MAX][MAX]; memset(dp, 0x3f, sizeof dp); // init to a value > 1.000.000.000 for (i = 0 ; i < n; i++) dp[i][0] = dp[0][i] = i; for (i = 1; i <= n; i++) { int from = max(1, i-k), to = min(i+k, n); for (j = from; j <= to; j++) { if (a[i-1] == b[j-1]) // same character dp[i][j] = dp[i-1][j-1]; // note that we don't allow letter substitutions dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]); // delete character j dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); // insert character i } } return dp[n][n]; } We only process 2*K+1 columns per row. So this algorithm works in O(N*K) which is fast enough.