Find if string is K | C ++ program to find if given string is K - Palindrome or not ; Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; L [ m ] [ n ] contains length of LCS for X and Y ; find if given string is K - Palindrome or not ; Find reverse of string ; find longest palindromic subsequence of given string ; If the difference between longest palindromic subsequence and the original string is less than equal to k , then the string is k - palindrome ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lcs ( string X , string Y , int m , int n ) { int L [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 j == 0 ) L [ i ] [ j ] = 0 ; else if ( X [ i - 1 ] == Y [ j - 1 ] ) L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 1 ; else L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) ; } } return L [ m ] [ n ] ; } bool isKPal ( string str , int k ) { int n = str . length ( ) ; string revStr = str ; reverse ( revStr . begin ( ) , revStr . end ( ) ) ; int lps = lcs ( str , revStr , n , n ) ; return ( n - lps <= k ) ; } int main ( ) { string str = " abcdeca " ; int k = 2 ; isKPal ( str , k ) ? cout << " Yes " : cout << " No " ; return 0 ; }