## Monday, June 6, 2016

### Find if string is K-Palindrome or not - GeeksforGeeks

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.
1. 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.
2. 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);`
`}`
http://www.geeksforgeeks.org/find-if-string-is-k-palindrome-or-not-set-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.
1. Reverse the given sequence and store the reverse in another array say rev[0..n-1]
2. 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 not`
`bool` `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.
1. 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.
2. 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 not`
`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);`
`}`

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.
1. 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.
2. 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 not`
`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);`
`}`
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.
`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.
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.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)
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]).
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])
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])
`  ``/* 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];`
`  ``}`