Input: “aba”
Output: True

Input: “abca”
Output: True

foflow-up:如果删掉k个字符呢？

``````public boolean validPalindrome(String s) {
int l = -1, r = s.length();
while (++l < --r)
if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);
return true;
}

public boolean isPalindromic(String s, int l, int r) {
while (++l < --r)
if (s.charAt(l) != s.charAt(r)) return false;
return true;
}
``````
1. Valid Palindrome III

Given a string `s` and an integer `k` , find out if the given string is a K-Palindrome or not.

A string is K-Palindrome if it can be transformed into a palindrome by removing at most `k` characters from it.

Example 1:

Input: s = “abcdeca”, k = 2 Output: true

Explanation: Remove ‘b’ and ‘e’ characters.

Constraints:

• `1 <= s.length <= 1000`
• `s` has only lowercase English letters.
• `1 <= k <= s.length`
No.1 voted discussion

The idea is to find the longest palindromic subsequence(lps) of the given string.
|lps - original string| <= k,
then the string is k-palindrome.

Eg:

One of the lps of string pqrstrp is prsrp.
Characters not contributing to lps of the
string should be removed in order to make the string palindrome
. So on removing q and s (or t) from pqrstrp, string will transform into a palindrome.

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

StringBuilder stringBuilder = new StringBuilder(str).reverse();
int lps = lcs(str, stringBuilder.toString(), n, n);

return (n - lps <= k);
}

/*
longest palindromic subsequence:
LCS of the given string & its reverse will be the longest palindromic sequence.
*/
private 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];
}
``````