Valid Palindrome III (Longest Palindromic Subsequence varation)

95.Valid Palindrome III

String

Dynamic Programming

Problem Statement:

Given a string s and an integer k, return true if s can be transformed into a palindrome by removing at most k characters. Otherwise, return false.

Algorithm:

1. Use a 2D dynamic programming (DP) table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].
2. Initialize dp[j][j] to 1 for all indices j, as a single character is always a palindrome.
3. Iterate over all possible ending indices j and starting indices i:
• If the characters s[i] and s[j] are the same, then dp[i][j] = dp[i + 1][j - 1] + 2.
• Otherwise, dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
4. Calculate the number of characters to remove to make the string a palindrome as diff = s.length() - dp[0][n-1].
5. Return true if diff ≤ k, otherwise false.

Complexity:

Time: O(n²), where n is the length of the string | Space: O(n²) for the DP table.

Java Implementation:

public class Solution {
    public boolean isValidPalindrome(String s, int k) {
        int[][] dp = new int[s.length()][s.length()]; // DP table

        // Build the DP table
        for (int j = 0; j < s.length(); j++) {
            dp[j][j] = 1; // A single character is always a palindrome
            for (int i = j - 1; i >= 0; i--) {
                if (s.charAt(j) == s.charAt(i)) 
                    dp[i][j] = dp[i + 1][j - 1] + 2; // Characters match
                else 
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]); // Take the max length
            }
        }

        // Calculate the number of characters to remove
        int diff = s.length() - dp[0][s.length() - 1];

        // Check if the difference is within k
        return diff <= k;
    }
}

Python Implementation:

def isValidPalindrome(s, k):
    n = len(s)
    dp = [[0] * n for _ in range(n)]  # DP table

    # Build the DP table
    for j in range(n):
        dp[j][j] = 1  # A single character is always a palindrome
        for i in range(j - 1, -1, -1):
            if s[i] == s[j]:  # Characters match
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])  # Take the max length

    # Calculate the number of characters to remove
    diff = n - dp[0][n - 1]

    # Check if the difference is within k
    return diff <= k

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        vector> dp(n, vector(n, 0)); // DP table

        // Build the DP table
        for (int j = 0; j < n; j++) {
            dp[j][j] = 1; // A single character is always a palindrome
            for (int i = j - 1; i >= 0; i--) {
                if (s[i] == s[j]) 
                    dp[i][j] = dp[i + 1][j - 1] + 2; // Characters match
                else 
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); // Take the max length
            }
        }

        // Calculate the number of characters to remove
        int diff = n - dp[0][n - 1];

        // Check if the difference is within k
        return diff <= k;
    }
};