K – Palindromic String (DP-19)

You are given a string and a positive integer K. You need to determine if the string is K palindrome or not. A string is called K palindrome, if it can be converted to a palindrome by removing at most K characters from it.

Sample Input: “CABCBC”, K = 2
Expected Output: “YES”
Explanation: You can remove ‘A’ after which the string becomes “CBCBC” which is a palindrome.

Algorithm:

The problem can be solved using Dynamic Programming as it has both optimal substructure and overlapping sub problem. The problem is a variation of Longest Palindromic Subsequence. We recommend you to check it out before solving this problem.

1. In order to make a string palindrome, the characters which does not contribute to Longest palindromic Subsequence can be removed.
2. So, if the difference between the length of the longest Palindromic subsequence and the length of the string is less than or equal to K, then the string is K – Palindromic.

#include <bits/stdc++.h>
using namespace std;

int helper(string X){
	//Longest Palindromic Subsequence
	int n = X.size();
	string Y = X;
	reverse(Y.begin(), Y.end());
	vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(X[i-1]==Y[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	return dp[n][n];
}

int main(){
	string X = "CABCBC";
	int K=2;
	if(X.size()-helper(X) <= K){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
	return 0;
}

Also, check out another popular interview problem Egg Dropping Puzzle.