Find if string is K | C ++ program to find if given string is K - Palindrome or not ; find if given string is K - Palindrome or not ; Create a table to store results of subproblems ; Fill dp [ ] [ ] in bottom up manner ; If first string is empty , only option is to remove all characters of second string ; If second string is empty , only option is to remove all characters of first string ; If last characters are same , ignore last character and recur for remaining string ; If last character are different , remove it and find minimum ; dp [ i ] [ j ] = 1 + min ( dp [ i - 1 ] [ j ] , Remove from str1 dp [ i ] [ j - 1 ] ) ; Remove from str2 ; Returns true if str is k palindrome . ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int isKPalDP ( string str1 , string str2 , int m , int n ) { int dp [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 ) else if ( j == 0 ) else if ( str1 [ i - 1 ] == str2 [ j - 1 ] ) dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] ; else } } return dp [ m ] [ n ] ; } bool isKPal ( string str , int k ) { string revStr = str ; reverse ( revStr . begin ( ) , revStr . end ( ) ) ; int len = str . length ( ) ; return ( isKPalDP ( str , revStr , len , len ) <= k * 2 ) ; } int main ( ) { string str = " acdcb " ; int k = 2 ; isKPal ( str , k ) ? cout << " Yes " : cout << " No " ; return 0 ; }