1216. Valid Palindrome III
Tags: ‘String’, ‘Dynamic Programming’
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 <= 1000shas only lowercase English letters.1 <= k <= s.length
Solution
Refer to 516. Longest Palindromic Subsequence
if k >= s.length() - lps then true
public boolean isValidPalindrome(String s, int k) {
int lps = longestPalindromeSubseq(s);
if (k >= s.length() - lps) return true;
else return false;
}
private int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < s.length(); 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][s.length() - 1];
}