1216

1216. Valid Palindrome III (Hard)

Given a string s and an integer k, return true if s is a k-palindrome.

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.

Example 2:

Input: s = "abbababa", k = 1
Output: true

 

Constraints:

• 1 <= s.length <= 1000
• s consists of only lowercase English letters.
• 1 <= k <= s.length

Companies:
Facebook

Related Topics:
String, Dynamic Programming

Solution 1. Longest Common Subsequence (LCS)

// OJ: https://leetcode.com/problems/valid-palindrome-iii/
// Author: github.com/lzl124631x
// 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();
    }
};