Find if string is K-Palindrome or not - GeeksforGeeks
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.
http://www.geeksforgeeks.org/find-if-string-is-k-palindrome-or-not-set-2/
Solving K-Palindrome problem using Edit distance algorithm | coding hangover
http://xiaohuiliucuriosity.blogspot.com/2015/03/k-palindrome.html
O(kn): Any position more than K positions away from the main diagonal is useless because its edit distance must exceed those K deletions. We only process 2*K+1 columns per row, k columns from the diagonal on each side.
Key: s is k-palindrome <=> editDistance(s, reverse(s)) <= 2k
editDistance is O(n^2) using DP.
https://linzhongzl.wordpress.com/2013/11/25/k-palindrome/
http://xiaohuiliucuriosity.blogspot.com/2015/03/k-palindrome.html
http://stackoverflow.com/questions/20892506/determine-if-a-given-string-is-a-k-palindrome
O(2^N)
Change string to char array => subString in java 8 is O(n) now - not O(1).
http://www.quora.com/A-k-palindrome-is-a-string-which-transforms-into-a-palindrome-on-removing-at-most-k-characters-from-it-Given-a-string-S-and-an-interger-K-find-whether-S-is-a-k-palindrome-or-not-Constraints-S-has-at-most-20-000-characters-and-0-k-30
http://www.geeksforgeeks.org/?p=12998
Dynamic Programming | Set 4 (Longest Common Subsequence)
Read full article from Find if string is K-Palindrome or not - GeeksforGeeks
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.
If we carefully analyze the problem, the task is to transform the given string into its reverse by removing at most K characters from it. The problem is basically a variation of Edit Distance. We can modify the Edit Distance problem to consider given string and its reverse as input and only operation allowed is deletion. Since given string is compared with its reverse, we will do at most N deletions from first string and N deletions from second string to make them equal. Therefore, for a string to be k-palindrome, 2*N <= 2*K should hold true. Below are the detailed steps of algorithm - Process all characters one by one staring from either from left or right sides of both strings. Let us traverse from the right corner, there are two possibilities for every pair of character being traversed.
- If last characters of two strings are same, we ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1 where m is length of str1 and n is length of str2.
- If last characters are not same, we consider remove operation on last character of first string and last character of second string, recursively compute minimum cost for the operations and take minimum of two values.
- Remove last char from str1: Recur for m-1 and n.
- Remove last char from str2: Recur for m and n-1.
int isKPalRec(string str1, string str2, int m, int n){ // If first string is empty, the only option is to // remove all characters of second string if (m == 0) return n; // If second string is empty, the only option is to // remove all characters of first string if (n == 0) return m; // If last characters of two strings are same, ignore // last characters and get count for remaining strings. if (str1[m-1] == str2[n-1]) return isKPalRec(str1, str2, m-1, n-1); // If last characters are not same, // 1. Remove last char from str1 and recur for m-1 and n // 2. Remove last char from str2 and recur for m and n-1 // Take minimum of above two operations return 1 + min(isKPalRec(str1, str2, m-1, n), // Remove from str1 isKPalRec(str1, str2, m, n-1)); // Remove from str2}// Returns true if str is k palindrome.bool isKPal(string str, int k){ string revStr = str; reverse(revStr.begin(), revStr.end()); int len = str.length(); return (isKPalRec(str, revStr, len, len) <= k*2);}int isKPalDP(string str1, string str2, int m, int n){ // Create a table to store results of subproblems int dp[m + 1][n + 1]; // Fill dp[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If first string is empty, only option is to // remove all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j // If second string is empty, only option is to // remove all characters of first string else if (j == 0) dp[i][j] = i; // Min. operations = i // If last characters are same, ignore last character // and recur for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If last character are different, remove it // and find minimum else dp[i][j] = 1 + min(dp[i - 1][j], // Remove from str1 dp[i][j - 1]); // Remove from str2 } } return dp[m][n];}// Returns true if str is k palindrome.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);}
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.
Auxiliary space used by the program is O(n2). It can further be reduced to O(n) by using Space Optimized Solution of LCS.
/* 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);}
If we carefully analyze the problem, the task is to transform the given string into its reverse by removing at most K characters from it. The problem is basically a variation of Edit Distance. We can modify the Edit Distance problem to consider given string and its reverse as input and only operation allowed is deletion. Since given string is compared with its reverse, we will do at most N deletions from first string and N deletions from second string to make them equal. Therefore, for a string to be k-palindrome, 2*N <= 2*K should hold true. Below are the detailed steps of algorithm - Process all characters one by one staring from either from left or right sides of both strings. Let us traverse from the right corner, there are two possibilities for every pair of character being traversed.
- If last characters of two strings are same, we ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1 where m is length of str1 and n is length of str2.
- If last characters are not same, we consider remove operation on last character of first string and last character of second string, recursively compute minimum cost for the operations and take minimum of two values.
- Remove last char from str1: Recur for m-1 and n.
- Remove last char from str2: Recur for m and n-1.
This problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, re-computations of same subproblems can be avoided by constructing a temporary array that stores results of subproblems .
// find if given string is K-Palindrome or notint isKPalDP(string str1, string str2, int m, int n){ // Create a table to store results of subproblems int dp[m + 1][n + 1]; // Fill dp[][] in bottom up manner for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // If first string is empty, only option is to // remove all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j // If second string is empty, only option is to // remove all characters of first string else if (j == 0) dp[i][j] = i; // Min. operations = i // If last characters are same, ignore last character // and recur for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If last character are different, remove it // and find minimum else dp[i][j] = 1 + min(dp[i - 1][j], // Remove from str1 dp[i][j - 1]); // Remove from str2 } } return dp[m][n];}// Returns true if str is k palindrome.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);}
If we carefully analyze the problem, the task is to transform the given string into its reverse by removing at most K characters from it. The problem is basically a variation of Edit Distance. We can modify the Edit Distance problem to consider given string and its reverse as input and only operation allowed is deletion. Since given string is compared with its reverse, we will do at most N deletions from first string and N deletions from second string to make them equal. Therefore, for a string to be k-palindrome, 2*N <= 2*K should hold true. Below are the detailed steps of algorithm - Process all characters one by one staring from either from left or right sides of both strings. Let us traverse from the right corner, there are two possibilities for every pair of character being traversed.
- If last characters of two strings are same, we ignore last characters and get count for remaining strings. So we recur for lengths m-1 and n-1 where m is length of str1 and n is length of str2.
- If last characters are not same, we consider remove operation on last character of first string and last character of second string, recursively compute minimum cost for the operations and take minimum of two values.
- Remove last char from str1: Recur for m-1 and n.
- Remove last char from str2: Recur for m and n-1.
// find if given string is K-Palindrome or notint isKPalRec(string str1, string str2, int m, int n){ // If first string is empty, the only option is to // remove all characters of second string if (m == 0) return n; // If second string is empty, the only option is to // remove all characters of first string if (n == 0) return m; // If last characters of two strings are same, ignore // last characters and get count for remaining strings. if (str1[m-1] == str2[n-1]) return isKPalRec(str1, str2, m-1, n-1); // If last characters are not same, // 1. Remove last char from str1 and recur for m-1 and n // 2. Remove last char from str2 and recur for m and n-1 // Take minimum of above two operations return 1 + min(isKPalRec(str1, str2, m-1, n), // Remove from str1 isKPalRec(str1, str2, m, n-1)); // Remove from str2}// Returns true if str is k palindrome.bool isKPal(string str, int k){ string revStr = str; reverse(revStr.begin(), revStr.end()); int len = str.length(); return (isKPalRec(str, revStr, len, len) <= k*2);}http://xiaohuiliucuriosity.blogspot.com/2015/03/k-palindrome.html
O(kn): Any position more than K positions away from the main diagonal is useless because its edit distance must exceed those K deletions. We only process 2*K+1 columns per row, k columns from the diagonal on each side.
int ModifiedEditDistance(const string& a, const string& b, int k) { int i, j, n = a.size(); // for simplicity. we should use only a window of size 2*k+1 or // dp[2][MAX] and alternate rows. only need row i-1 int dp[MAX][MAX]; memset(dp, 0x3f, sizeof dp); // init dp matrix to a value > 1.000.000.000 for (i = 0 ; i < n; i++) dp[i][0] = dp[0][i] = i; for (i = 1; i <= n; i++) { int from = max(1, i-k), to = min(i+k, n); for (j = from; j <= to; j++) { if (a[i-1] == b[j-1]) // same character dp[i][j] = dp[i-1][j-1]; // note that we don't allow letter substitutions dp[i][j] = min(dp[i][j], 1 + dp[i][j-1]); // delete character j dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); // insert character i } } return dp[n][n];}
This can be solved using Edit distance dynamic programming algorithm. Edit distance DP algorithm can be used to find the minimum operations required to convert a source string to destination string. The operations can be either addition or deletion of characters.
The K-palindrome problem can be solved using Edit distance algorithm by checking if the minimum operation required to convert the input string to its reverse.
Let editDistance(source,destination) be the function which takes source string and destination string and returns the minimum operations required to convert the source string to destination string.
A string S is K-palindrome if editDistance(S,reverse(S))<=2*K
This is because we can transform the given string S into its reverse by deleting K letters and then inserting K letters.
This will be more clear with an example.
Let S=madtam and K=1.
To convert it into reverse of S, i.e matdam first we have to remove the character at index 3 ( 0 based index) in S.
Now the intermediate string is madam . Then we have to insert the character t at index 2 in the intermediate string to get “matdam” which is the reverse of string s.
If you look carefully you will know that the intermediate string “madam” is the palindrome that is obtained by removing k=1 characters.
O(n^2)Key: s is k-palindrome <=> editDistance(s, reverse(s)) <= 2k
editDistance is O(n^2) using DP.
https://linzhongzl.wordpress.com/2013/11/25/k-palindrome/
public static boolean isKPalindrome(String source, int k){ return k == editDistance(source)/2;}public static int editDistance(String source){ int n= source.length(); int[][] distance=new int[n+1][n+1]; for(int i=0;i<=n;i++){ distance[i][0]=i; } for(int j=0;j<=n;j++){ distance[0][j]=j; } for(int j=1;j<=n;j++){ for(int i=1;i<=n;i++){ if(source.charAt(i-1)==source.charAt(n-1-(j-1))){ distance[i][j]=distance[i-1][j-1]; } else{ distance[i][j]= Math.min((distance[i-1][j]+1),(distance[i][j-1]+1)); } } } return(distance[n][n]); }public static void main(String[] args) { System.out.println(isKPalindrome("abaxbabax", 2));}http://xiaohuiliucuriosity.blogspot.com/2015/03/k-palindrome.html
http://stackoverflow.com/questions/20892506/determine-if-a-given-string-is-a-k-palindrome
O(2^N)
Change string to char array => subString in java 8 is O(n) now - not O(1).
bool isKPalindrome(string s, int k) { if (s.size() <= 1) return true; if (0 == k) return s[0] == s[s.size() - 1] && isKPalindrome(s.substr(1, s.size() - 2), k); if (s[0] == s[s.size() - 1]) return isKPalindrome(s.substr(1, s.size() - 2), k); else return isKPalindrome(s.substr(0, s.size() - 1), k - 1) || isKPalindrome(s.substr(1, s.size() - 1), k - 1);}http://www.geeksforgeeks.org/?p=12998
Dynamic Programming | Set 4 (Longest Common Subsequence)
1) Optimal Substructure:
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).
If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char[] X, char[] Y, int m, int n ) { if (m == 0 || n == 0) return 0; if (X[m-1] == Y[n-1]) return 1 + lcs(X, Y, m-1, n-1); else return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); } /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char[] X, char[] 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] = max(L[i-1][j], L[i][j-1]); } } return L[m][n]; }