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.
Examples:
Input : String - abcdecba, k = 1 Output : Yes String can become palindrome by removing 1 character i.e. either d or e Input : String - abcdeca, K = 2 Output : Yes Can become palindrome by removing 2 characters b and e (or b and d). Input : String - acdcb, K = 1 Output : No String can not become palindrome by removing only one character.
We have discussed a DP solution in previous post where we saw that the problem is basically a variation of Edit Distance problem. In this post, another interesting DP solution is discussed.
The idea is to find the longest palindromic subsequence of the 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 else it is not k-palindrome.
For example, longest palindromic subsequence of string abcdeca is acdca(or aceca). The characters which do not contribute to longest palindromic subsequence of the string should be removed in order to make the string palindrome. So on removing b and d (or e) from abcdeca, string will transform into a palindrome.
Longest palindromic subsequence of a string can easily be found using LCS. Following is the two step solution for finding longest palindromic subsequence that uses LCS.
- Reverse the given sequence and store the reverse in another array say rev[0..n-1]
- LCS of the given sequence and rev[] will be the longest palindromic sequence.
Below is the implementation of above idea –
CPP
// C++ program to find if given string is K-Palindrome// or not#include <bits/stdc++.h>using namespace std;/* Returns length of LCS for X[0..m-1], Y[0..n-1] */int lcs( string X, string Y, int m, int n ){ int L[m + 1][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] */ 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]); } } // L[m][n] contains length of LCS for X and Y return L[m][n];}// find if given string is K-Palindrome or notbool isKPal(string str, int k){ int n = str.length(); // Find reverse of string string revStr = str; reverse(revStr.begin(), revStr.end()); // find longest palindromic subsequence of // given string int lps = lcs(str, revStr, n, n); // If the difference between longest palindromic // subsequence and the original string is less // than equal to k, then the string is k-palindrome return (n - lps <= k);}// Driver programint main(){ string str = "abcdeca"; int k = 2; isKPal(str, k) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java program to find if given // String is K-Palindrome or notimport java.util.*;import java.io.*;class GFG { /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ static int lcs(String X, String Y, int m, int n) { int L[][] = new int[m + 1][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] */ 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.charAt(i - 1) == Y.charAt(j - 1)) { L[i][j] = L[i - 1][j - 1] + 1; } else { L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]); } } } // L[m][n] contains length // of LCS for X and Y return L[m][n]; } // find if given String is // K-Palindrome or not static boolean isKPal(String str, int k) { int n = str.length(); // Find reverse of String StringBuilder revStr = new StringBuilder(str); revStr = revStr.reverse(); // find longest palindromic // subsequence of given String int lps = lcs(str, revStr.toString(), n, n); // If the difference between longest // palindromic subsequence and the // original String is less than equal // to k, then the String is k-palindrome return (n - lps <= k); } // Driver code public static void main(String[] args) { String str = "abcdeca"; int k = 2; if (isKPal(str, k)) { System.out.println("Yes"); } else System.out.println("No"); }}// This code is contributed by Rajput-JI |
Python3
# Python program to find# if given string is K-Palindrome# or not# Returns length of LCS# for X[0..m-1], Y[0..n-1] def lcs(X, Y, m, n ): L = [[0]*(n+1) for _ in range(m+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] for i in range(m+1): for j in range(n+1): if not i or not j: L[i][j] = 0 elif 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]) # L[m][n] contains length # of LCS for X and Y return L[m][n]# find if given string is# K-Palindrome or notdef isKPal(string, k): n = len(string) # Find reverse of string revStr = string[::-1] # find longest palindromic # subsequence of # given string lps = lcs(string, revStr, n, n) # If the difference between # longest palindromic # subsequence and the original # string is less # than equal to k, then # the string is k-palindrome return (n - lps <= k)# Driver programstring = "abcdeca"k = 2print("Yes" if isKPal(string, k) else "No")# This code is contributed# by Ansu Kumari. |
C#
// C# program to find if given // String is K-Palindrome or not using System;class GFG { /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ static int lcs(String X, String Y, int m, int n) { int [,]L = new int[m + 1,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] */ 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] = Math.Max(L[i - 1, j], L[i, j - 1]); } } } // L[m,n] contains length // of LCS for X and Y return L[m, n]; } // find if given String is // K-Palindrome or not static bool isKPal(String str, int k) { int n = str.Length; // Find reverse of String str = reverse(str); // find longest palindromic // subsequence of given String int lps = lcs(str, str, n, n); // If the difference between longest // palindromic subsequence and the // original String is less than equal // to k, then the String is k-palindrome return (n - lps <= k); } static String reverse(String input) { char[] temparray = input.ToCharArray(); int left, right = 0; right = temparray.Length - 1; for (left = 0; left < right; left++, right--) { // Swap values of left and right char temp = temparray[left]; temparray[left] = temparray[right]; temparray[right] = temp; } return String.Join("",temparray); } // Driver code public static void Main(String[] args) { String str = "abcdeca"; int k = 2; if (isKPal(str, k)) { Console.WriteLine("Yes"); } else Console.WriteLine("No"); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to find// if given string is K-Palindrome// or not// Returns length of LCS// for X[0..m-1], Y[0..n-1] function lcs(X, Y, m, n ){ let L = new Array(m+1); for(let i=0;i<m+1;i++){ L[i] = new Array(n+1).fill(0); } // 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] for(let i = 0; i < m + 1; i++) { for(let j = 0; j < n + 1; j++) { if(!i || !j) 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] = Math.max(L[i - 1][j], L[i][j - 1]) } } // L[m][n] contains length // of LCS for X and Y return L[m][n]}// find if given string is// K-Palindrome or notfunction isKPal(string, k){ let n = string.length // Find reverse of string let revStr = string.split("").reverse().join("") // find longest palindromic // subsequence of // given string let lps = lcs(string, revStr, n, n) // If the difference between // longest palindromic // subsequence and the original // string is less // than equal to k, then // the string is k-palindrome return (n - lps <= k)}// Driver programlet string = "abcdeca"let k = 2document.write(isKPal(string, k)?"Yes" : "No")// This code is contributed by shinjanpatra</script> |
Output
Yes
Time complexity of above solution is O(n2).
Auxiliary space used by the program is O(n2). It can further be reduced to O(n) by using Space Optimized Solution of LCS.
Thanks to Ravi Teja Kaveti for suggesting above solution.
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
