Home »
Interview coding problems/challenges
K-Palindromic String
K-Palindromic String: Here, we are going to check whether a given string is k-palindromic string or not?
Submitted by Divyansh Jaipuriyar, on August 18, 2020
Problem statement:
Given a string, find out if the string is K-palindrome or not. A k-palindrome string transforms into a palindrome on removing at most k characters from it.
Problem description:
The given problem needs knowledge of palindrome, which is a string whose structure from first to the last traversal is the same as traversal from last to the first position.
You have to check if the given string is K-palindrome it means after removing at maximum k number of characters from the string is converted into some kind of palindrome. If possible then print "YES" otherwise print "NO".
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the integers N and K where N denotes the length of the string.
The second line of each test case contains the string.
Output:
Print YES if the given string is K-palindrome else print NO. Print the answer for each test case in a new line.
Constraints:
1<= T <=100
1<= N, K <=1000
Examples:
Input:
T=1
abcdedecbaef
k=3
Output:
YES
Input:
T=1
abcde
k=3
Output:
NO
Solution approach:
1) Recursive Approach:
This problem is an application of EDIT DISTANCE of dynamic problem, but the main logic here is that we will use one string as the given string and the other string as the reverse of the given string and the only operation that we can perform is delete and no other option of Edit distance logic.
To make the two string equal we need to almost N deletions from each string that is 2*N deletion overall, therefore if 2*N<=2*k then only the string is K-palindrome.
We will follow this algorithm:
if any of the string is empty
then return total length of
other string.
if last character of both string are
same then recur for remaining character.
if last character are not same then
first case: remove last character from first
string and recur.
second case: remove last character from
second string and recur.
return 1+min(first case, second case)
Time Complexity for the above approach in the worst case is exponential.
Space Complexity for the above approach in the worst case is linear.
2) Dynamic Programming Approach:
(a): Top Down Approach:
In this approach we will use memorization method, we will create 2-D dp[n][m] state where initially all the states are filled with -1, then each time we call recurrence function we update the dp[n][m] state, where n is the index for first string and m is the index for the second string.
(b) Bottom Up Approach:
In this approach we will fill the table in bottom up manner, each dp[n][m] state will be filled in bottom up manner as initially for state of length (i==0 or j==0) we will give them the value of other string length(i+j),i.t dp[i][j]=(i+j) if i==0||j==0.
dp[i][j]=(i+j),i==0 or j==0.
if(s1[i-1]==s2[j-1])
dp[i][j]=dp[i-1][j-1],i>=1 and j>=1
else
dp[i][j]=1+min(dp[i-1][j],dp[i][j-1])
Here, s1 is given string, s2 is the reversed form of s1, i and j are the length of s1 and s2 at dp[][] state i and j respectively.
Time complexity for the above approach in the worst case is : O(n*n)
Space complexity for the above approach in the worst case is : O(n*n)
C++ Implementation (Recursive Approach):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//solve function which will
//return minimum delete operation
//to make two string equal.
ll solve(string s1, string s2, ll n, ll m)
{
//if either string is of 0 length
//remove all characters from the
//other string.
if (n == 0 || m == 0)
return (n + m);
//if last character are same
//then recur for remaining characters.
if (s1[n - 1] == s2[m - 1])
return solve(s1, s2, n - 1, m - 1);
else //find minimum from two possible case
//at one if last character of first string is
//excluded and in other case if last character of
//second string is excluded.
return 1 + min(solve(s1, s2, n - 1, m), solve(s1, s2, n, m - 1));
}
int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;
while (t--) {
cout << "Enter string: ";
string s1;
cin >> s1;
cout << "Enter K: ";
ll k;
cin >> k;
//for reversed string.
string s2 = s1;
ll n = s1.length();
//reverse.
reverse(s2.begin(), s2.end());
if (solve(s1, s2, n, n) <= 2 * k)
cout << "YES"
<< "\n";
else
cout << "NO"
<< "\n";
}
return 0;
}
Output:
Enter number of test cases: 3
Enter string: abcccdcccab
Enter K: 1
NO
Enter string: abcdba
Enter K: 1
YES
Enter string: include
Enter K: 2
NO
C++ Implementation (Dynamic Programming Approach):
(a) Top Down Approach:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//initialize dp state.
ll dp[1003][1003];
//solve function which will
//return minimum delete operation
//to make two string equal.
ll solve(string s1, string s2, ll n, ll m)
{
//if either string is of 0 length
//remove all characters from the
//other string.
if (n == 0 || m == 0)
return (n + m);
//if already calculated then
//simply return.
if (dp[n][m] != -1)
return dp[n][m];
//if last character are same
//then recur for remaining characters.
if (s1[n - 1] == s2[m - 1])
return dp[n][m] = solve(s1, s2, n - 1, m - 1);
else //find minimum from two possible case
//at one if last character of first string is
//excluded and in other case if last character of
//second string is excluded.
return dp[n][m] = 1 + min(solve(s1, s2, n - 1, m), solve(s1, s2, n, m - 1));
}
int main()
{
ll t;
cout << "Enter number of test cases: ";
cin >> t;
while (t--) {
cout << "Enter string: ";
string s1;
cin >> s1;
cout << "Enter K: ";
ll k;
cin >> k;
//for reversed string.
string s2 = s1;
ll n = s1.length();
//initially fill all dp state
//with -1.
memset(dp, -1, sizeof(dp));
//reverse.
reverse(s2.begin(), s2.end());
if (solve(s1, s2, n, n) <= 2 * k)
cout << "YES"
<< "\n";
else
cout << "NO"
<< "\n";
}
return 0;
}
Output:
Enter number of test cases: 2
Enter string: abbbaaabbbaaadce
Enter K: 3
NO
Enter string: abcdefghfedcba
Enter K: 3
YES
(b) Bottom Up Approach
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cout << "Enter number of test case: ";
cin >> t;
while (t--) {
cout << "Enter string: ";
string s1;
cin >> s1;
string s2;
s2 = s1;
ll k;
cout << "Enter K: ";
cin >> k;
reverse(s2.begin(), s2.end());
ll n = s1.length();
//initialise dp state.
ll dp[n + 1][n + 1];
for (ll i = 0; i <= n; i++)
for (ll j = 0; j <= n; j++) {
//if either of them is 0.
if (i == 0 || j == 0) {
dp[i][j] = (i + j);
continue;
}
else {
//if character matches
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else //if there last character does not matches.
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
}
}
ll z = dp[n][n];
//if deletions count is less
//than 2*k then it is possible to
//make two string identical.
if (z <= 2 * k)
cout << "YES"
<< "\n";
else
cout << "NO"
<< "\n";
}
return 0;
}
Output:
Enter number of test case: 3
Enter string: abcdef
Enter K: 3
NO
Enter string: abcde
Enter K: 3
NO
Enter string: abcdedecbaef
Enter K: 3
YES