1216. Valid Palindrome III

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

Solution:

class Solution {
    public boolean isValidPalindrome(String s, int k) {
        int left = 0;
        int right = s.length() - 1;

        while(left <= right){
            if (s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            }else{
                // != 
                if (k > 0){
                    k--;
                    return isParlindrome(s, left + 1, right, k) || isParlindrome(s, left, right - 1, k);
                }else{
                    return false;
                }

            }

        }

        return true;
    }

    private boolean isParlindrome(String s, int left, int right, int k){
        while(left <= right){
            if (s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            }else{
                if (k > 0){
                    k--;
                    return isParlindrome(s, left + 1, right, k) || isParlindrome(s, left, right - 1, k);
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}
// TLE
// SC: O(n)
// SC: O(n)

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

        for (int i = s.length() - 2; i >= 0; i--){
            for (int j = i + 1; j < s.length(); j++){
                if (s.charAt(i) == s.charAt(j)){
                    memo[i][j] = memo[i + 1][j - 1];
                }else{
                    memo[i][j] = 1 + Math.min(memo[i + 1][j], memo[i][j - 1]);
                }
            }
        }

        return memo[0][s.length() - 1] <= k;
    }
}

72. Edit Distance

516. Longest Palindromic Subsequence