Problem Statement

 Given a string s and an integer k, return true if the string can be a palindrome after deleting at most k characters.

Constraints

1 <= s.length <= 1000
s has only lowercase English letters.
1 <= k <= s.length

Examples

Example 1:

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

Different Approaches

1️⃣ Recursion (Brute Force Approach)

🔍 Idea:

• Try all possible ways to delete characters and check if any lead to a palindrome. At each mismatch, recursively try:
• deleting the left character
• deleting the right character

Code:

// Function to check if a string can be a palindrome 
// by removing at most 'k' characters between indices i and j
bool isPalindrome(string& s, int i, int j, int k) {

    // Base case: if we've used more deletions than allowed (k < 0), it's not valid
    if (k < 0) return false;

    // Loop from both ends towards the center
    while (i < j) {

        // If characters at current positions don't match
        if (s[i] != s[j]) {
            // Try both options:
            // 1. Remove character at the left (i) and decrease k
            // 2. Remove character at the right (j) and decrease k
            // If either leads to a valid palindrome, return true
            return isPalindrome(s, i + 1, j, k - 1) || isPalindrome(s, i, j - 1, k - 1);
        }

        // If characters match, move both pointers inward
        i++;
        j--;
    }

    // If loop completes, it means it's a palindrome within the allowed deletions
    return true;
}

Complexity Analysis:

• Time Complexity:O(2 ^ n)
• Space Complexity:O(n)
  • Recursion call stack

2️⃣ Memoization

🔍 Idea:

• Optimize brute force by storing results for (i, j, k) in a DP table to avoid re-computation.

Code:

class Solution {
public:
    // Helper function to check if the substring s[left...right]
    // can be a palindrome by removing at most 'remainingDeletes' characters
    bool canBePalindrome(string& s, int left, int right, int remainingDeletes, vector<vector<int>>& dp) {
        // Base Case: If left crosses or meets right, it's already a palindrome
        if (left >= right) return true;

        // If we've already computed the result for this substring, return it
        if (dp[left][right] != -1) return dp[left][right];

        // If characters match, move inward
        if (s[left] == s[right]) {
            dp[left][right] = canBePalindrome(s, left + 1, right - 1, remainingDeletes, dp);
        } else {
            // If characters don't match and we have no deletions left
            if (remainingDeletes == 0) {
                dp[left][right] = false;
            } else {
                // Try removing one character either from left or right
                bool removeLeft = canBePalindrome(s, left + 1, right, remainingDeletes - 1, dp);
                bool removeRight = canBePalindrome(s, left, right - 1, remainingDeletes - 1, dp);
                dp[left][right] = removeLeft || removeRight;
            }
        }

        return dp[left][right];
    }

    // Main function to check if string can be palindrome by removing at most k characters
    bool isValidPalindrome(string s, int k) {
        int n = s.size();

        // dp[i][j] stores whether s[i...j] can be a palindrome with at most k deletions
        vector<vector<int>> dp(n, vector<int>(n, -1));  // -1 means not computed yet

        // Call the helper from the full string with k deletions allowed
        return canBePalindrome(s, 0, n - 1, k, dp);
    }
};

Complexity Analysis:

• Time Complexity:O(n^2)
• Space Complexity: O(n^2)
  • Because of the recursion stack and dp array