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.
- In order to make a string palindrome, the characters which does not contribute to Longest palindromic Subsequence can be removed.
- 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.
2 comments