Valid Palindrome III

hard dynamic programming palindrome subsequence

Problem

Given a string s and an integer k, return true if s is a k-palindrome. A string is a k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Inputs = "abcdeca", k = 2

Outputtrue

Remove 'b' and 'e' to get "acdca", a palindrome. The longest palindromic subsequence is "acdca" of length 5, so we need 7 − 5 = 2 deletions ≤ k.

s (string)

def is_valid_palindrome(s, k):
    n = len(s)
    # dp[i][j] = longest palindromic subsequence in s[i..j]
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return n - dp[0][n - 1] <= k

function isValidPalindrome(s, k) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[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 n - dp[0][n - 1] <= k;
}

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

bool isValidPalindrome(string s, int k) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return n - dp[0][n - 1] <= k;
}

Explanation

To make s a palindrome by deleting characters, we should keep the largest palindrome already hidden inside it. That kept core is the longest palindromic subsequence (LPS), and the deletions we need equal n - LPS. If that count is ≤ k, the answer is true.

We compute the LPS with interval DP: dp[i][j] = length of the longest palindromic subsequence inside the slice s[i..j]. A single character is a palindrome of length 1, so dp[i][i] = 1.

For a wider slice we compare the two ends. If s[i] == s[j], both ends join the palindrome: dp[i][j] = dp[i+1][j-1] + 2. Otherwise we drop one end and take the better side: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

We fill i from high to low and j from low to high so the smaller inner slices are always ready before the bigger ones.

Example: s = "abcdeca", k = 2. The LPS is "acdca" of length 5, so deletions = 7 - 5 = 2 ≤ 2 → true.

Time: O(n²) Space: O(n²)