# LeetCode 1216. Valid Palindrome III

2021年09月15日 阅读数：7

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

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

Example 1:code

```Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.```

Constraints:orm

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

Find the longest palindrome from s.blog

And check the difference between s and longest palindrome length, if it is <= k, then return true.leetcode

Time Complexity: O(n^2). n = s.length().rem

Space: O(n^2).

AC Java:

``` 1 class Solution {
2     public boolean isValidPalindrome(String s, int k) {
3         if(s == null || s.length() <= k){
4             return true;
5         }
6
7         int lp = findLongestPalin(s);
8         return s.length() - lp <= k;
9     }
10
11     private int findLongestPalin(String s){
12         if(s == null || s.length() == 0){
13             return 0;
14         }
15
16         int n = s.length();
17         int [][] dp = new int[n][n];
18         for(int i = n-1; i>=0; i--){
19             dp[i][i] = 1;
20             for(int j = i+1; j<n; j++){
21                 if(s.charAt(i) == s.charAt(j)){
22                     dp[i][j] = dp[i+1][j-1] + 2;
23                 }else{
24                     dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
25                 }
26             }
27         }
28
29         return dp[0][n-1];
30     }
31 }```