原题链接在这里：https://leetcode.com/problems/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-
shas only lowercase English letters. 1 <= k <= s.length
题解：
Find the longest palindrome from s.
And check the difference between s and longest palindrome length, if it is <= k, then return true.
Time Complexity: O(n^2). n = s.length().
Space: O(n^2).
AC Java:
class Solution {
public boolean isValidPalindrome(String s, int k) {
if(s == null || s.length() <= k){
return true;
}
int lp = findLongestPalin(s);
return s.length() - lp <= k;
}
private int findLongestPalin(String s){
if(s == null || s.length() == 0){
return 0;
}
int n = s.length();
int [][] dp = new int[n][n];
for(int i = n-1; i>=0; i--){
dp[i][i] = 1;
for(int j = i+1; j<n; j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}else{
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
类似Longest Palindromic Subsequence, Valid Palindrome, Valid Palindrome II.