# Find if string is K-Palindrome or not

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.
```

```java
class Solution {
    public int lcs(String X, String Y, int m, int n) {
        int dp[][] = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = 0;
                else if (X.charAt(i - 1) == Y.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public boolean isKPal(String str, int k) {
        int n = str.length();

        // Find reverse of String
        StringBuilder revStr = new StringBuilder(str);
        revStr = revStr.reverse();

        int lps = lcs(str, revStr.toString(), n, n);

        return (n - lps <= k);
    }
}
```
