Formatted question description: https://leetcode.ca/all/1216.html

# 1216. Valid Palindrome III

Hard

## Description

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

This problem can be solved by first obtaining the length of the longest palindromic subsequence, and check whether the difference between the string’s length and the length of the longest palindromic subsequence is less than or equal to k.

To obtain the length of the longest palindromic subsequence, use the solution to problem 516.

• class Solution {
public boolean isValidPalindrome(String s, int k) {
int length = s.length();
int[][] dp = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < 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]);
}
}
int maxLength = dp[0][length - 1];
return length - maxLength <= k;
}
}

• // OJ: https://leetcode.com/problems/valid-palindrome-iii/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
bool isValidPalindrome(string s, int k) {
string t(s.rbegin(), s.rend());
int N = s.size();
vector<int> dp(N + 1);
for (int i = 0; i < N; ++i) {
int prev = 0;
for (int j = 0; j < N; ++j) {
int cur = dp[j + 1];
if (s[i] == t[j]) dp[j + 1] = 1 + prev;
else dp[j + 1] = max(dp[j + 1], dp[j]);
prev = cur;
}
}
return dp[N] + k >= s.size();
}
};

• print("Todo!")