1216. Valid Palindrome III

Posted on Edited on In

1216. Valid Palindrome III

Description

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:

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

Example 2:

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

Constraints:

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

Hints/Notes

  • 2025/01/19
  • dp
  • premium

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> dp;

    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        dp.resize(n, vector<int>(n, -1));
        int res = dfs(s, 0, n - 1);
        return res <= k;
    }

    int dfs(string& s, int left, int right) {
        if (left >= right) {
            return 0;
        }
        if (dp[left][right] != -1) {
            return dp[left][right];
        }
        int& res = dp[left][right];
        if (s[left] == s[right]) {
            res = dfs(s, left + 1, right - 1);
        } else {
            res = min(dfs(s, left, right - 1), dfs(s, left + 1, right)) + 1;
        }
        return res;
    }
};