Leetcode 1216. Valid Palindrome III

Problem Explanation

Given a string, we are required to figure out whether by eliminating at most k characters, the resultant string can be a palindrome. A palindrome string is one which reads the same backward as forwards, such as 'madam' or 'deed'.

For example, if the input string is 'cattc' and k is 1. By removing character 'a', the string can be transformed into a palindrome ('cttc' -> 'cattc') so it is a k-palindrome.

Approach

The solution to this problem uses dynamic programming, specifically the approach similar to finding the Longest Palindromic Subsequence (LPS). LPS is the length of the longest subsequence in a given string which is also palindrome. In dynamic programming, we break the problem into smaller problems and solve these smaller problems to get the solution to the big problem.

The algorithm involves initializing a 2D array (dp[][]) to store the length of the longest palindrome subsequence in the substring ranging from i to j ( dp[i][j]). The main idea is to iterate over the string, making a string range dynamically from i to j (both inclusive). For every range, check if the characters at index i and j of the string are equal.

• If they are equal, add 2 to the count for the range i+1 to j-1 ( dp[i+1][j-1] ).
• If they are unequal, we take the maximum (max) of the count for the ranges i+1 to j and i to j-1 which means we are removing either the character at position i or j to find the maximum length of the palindrome.

Finally return if the difference between the length of the input string and the length of the LPS found is equal or smaller than k.

Walkthrough Example

Suppose the input string is 'cattc' and k is 1. The length of string 'cattc' is 5. The length of LPS is 4 (substring 'cattc' or 'attca').

So the difference between the string length (5) and the LPS length (4) is 1, which is equal to k. So the string is a K-Palindrome.

1
2python
3#Making dynamic programming 2-D array 
4dp = [[0]*5 for _ in range(5)] 
5
6# We traverse from 'cattc' and the calculated dp array is:
7# [[1, 1, 2, 2, 4], 
8# [0, 1, 2, 2, 3], 
9# [0, 0, 1, 1, 2], 
10# [0, 0, 0, 1, 1], 
11# [0, 0, 0, 0, 1]]
12# The length of the LPS is 4 (dp[0][4]). 
13# So, the result is (5-4=1) <= 1 (k value), return True.

Python Solution

1
2python
3class Solution:
4    def isValidPalindrome(self, s: str, k: int) -> bool:
5        
6        # Find the length of the Longest Palindromic Subsequence (LPS)
7        def longestPalindromeSubseq(s: str) -> int:
8            n = len(s)
9            dp = [[0]*n for _ in range(n)] 
10
11            # every single character is a palindrome of length 1
12            for i in range(n):
13                dp[i][i] = 1
14
15            # traverse the string from reverse. 
16            for cl in range(2, n+1):
17                for i in range(n - cl + 1):
18                    j = i + cl - 1
19                    if s[i] == s[j] and cl == 2:
20                        # if there are only 2 characters and both are same
21                        dp[i][j] = 2
22                    elif s[i] == s[j]:
23                        # if the characters are same and more than 2 characters are there
24                        dp[i][j] = dp[i+1][j-1] + 2
25                    else:
26                        # if the characters are not same.
27                        dp[i][j] = max(dp[i][j-1], dp[i+1][j])
28            # maximum length will be at dp[0][n-1]
29            return dp[0][n-1]
30        
31        # length difference of s and LPS is less than or equal to k
32        return len(s) - longestPalindromeSubseq(s) <= k

Note: The similar solutions can be implemented in Java, JavaScript, C++, and C#.### Java Solution

Below is the Java code which uses the similar approach. We find the Longest Palindromic Subsequence (LPS) and then compare the difference between length of the string and LPS with the given k.

1
2java
3public class Solution {
4    public boolean isValidPalindrome(String s, int k) {
5        int length = getLongestPalindromicSubsequence(s);
6        return length >= s.length() - k;
7    }
8    
9    private int getLongestPalindromicSubsequence(String s) {
10        int n = s.length();
11        int[][] dp = new int[n][n];
12        
13        for (int i = 0; i < n; i++) {
14            dp[i][i] = 1;
15        }
16
17        for (int cl = 2; cl <= n; cl++) {
18            for (int i = 0; i < n - cl + 1; i++) {
19                int j = i + cl - 1;
20                if (s.charAt(i) == s.charAt(j) && cl == 2) {
21                    dp[i][j] = 2;
22                } else if (s.charAt(i) == s.charAt(j)) {
23                    dp[i][j] = dp[i+1][j-1] + 2;
24                } else {
25                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
26                }
27            }
28        }
29        return dp[0][n-1];
30    }
31}

JavaScript Solution

Below is the JavaScript code for the problem using a similar approach as discussed:

1
2javascript
3class Solution {
4    isValidPalindrome(s, k) {
5        let lps = this.getLongestPalindromicSubsequence(s);
6        return lps >= s.length - k;
7    }
8
9    getLongestPalindromicSubsequence(s) {
10        let n = s.length;
11        let dp = Array.from(Array(n), () => new Array(n).fill(0));
12        
13        for (let i = 0; i < n; i++) {
14            dp[i][i] = 1;
15        }
16        
17        for (let cl = 2; cl <= n; cl++) {
18            for (let i = 0; i < n - cl + 1; i++) {
19                let j = i + cl - 1;
20                if (s.charAt(i) == s.charAt(j) && cl == 2) {
21                    dp[i][j] = 2;
22                } else if (s.charAt(i) == s.charAt(j)) {
23                    dp[i][j] = dp[i+1][j-1] + 2;
24                } else {
25                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
26                }
27            }
28        }
29        return dp[0][n-1];
30    }
31}
32
33let sol = new Solution();
34console.log(sol.isValidPalindrome('cattc', 1)); // Outputs: true

All these solutions use dynamic programming to find the length of the longest palindromic subsequence and then check if this length difference from the length of the string is less than or equal to k. If it is, then we can say that the string can be transformed into a palindrome by removing at most k characters and we return true otherwise we return false.