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
Solution:
class Solution {
Integer[][] dp;
public boolean isValidPalindrome(String s, int k) {
dp = new Integer[s.length()][s.length()];
return helper(s, 0, s.length() - 1) <= k;
}
private int helper(String s, int left, int right) {
if (right < left) return 0;
if (dp[left][right] != null) return dp[left][right];
int ret = 0;
if (s.charAt(left) != s.charAt(right)) {
ret = 1 + Math.min(helper(s, left + 1, right), helper(s, left, right - 1));
} else {
ret = helper(s, left + 1, right - 1);
}
return dp[left][right] = ret;
}
}