LeetCode 1216 - Valid Palindrome III

The problem asks us to determine whether a given string s can become a palindrome after removing at most k characters. A palindrome is a string that reads the same forwards and backwards, and a k-palindrome is one that can be turned into a palindrome with at most k deletions.

leetcodehardstringdynamic-programming

LeetCode Problem 1216

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine whether a given string s can become a palindrome after removing at most k characters. A palindrome is a string that reads the same forwards and backwards, and a k-palindrome is one that can be turned into a palindrome with at most k deletions.

The input consists of a string s containing only lowercase English letters and an integer k. The output is a boolean value, true if the string is a k-palindrome and false otherwise.

The constraints tell us that the string can be up to length 1000, which is large enough that naive recursive solutions that explore all possible deletions would be too slow. k can range from 1 to the length of the string, meaning in some cases we may need to remove almost all characters.

Important edge cases include very short strings (length 1 or 2), strings that are already palindromes, strings that require exactly k deletions, and strings where k is larger than the number of deletions needed.

Approaches

A brute-force approach would attempt all possible ways of removing up to k characters and then checking if the resulting string is a palindrome. This approach works because it explores all possible valid transformations, but it is computationally infeasible. With a string of length n, there are combinatorially many subsets of characters to remove, leading to exponential time complexity.

The key insight for an optimal solution is to recognize that the problem is equivalent to finding the longest palindromic subsequence (LPS) in the string. Once we know the LPS length, we can compute the minimum deletions required as len(s) - LPS_length. If this number is less than or equal to k, the string is a k-palindrome. Dynamic programming is a natural fit here because we can build the LPS length using overlapping subproblems.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Explore all subsets of deletions and check for palindrome
Optimal O(n^2) O(n^2) Use DP to compute longest palindromic subsequence, then compare to k

Algorithm Walkthrough

  1. Define a 2D DP array dp[i][j] that represents the length of the longest palindromic subsequence of the substring s[i:j+1].
  2. Initialize dp[i][i] = 1 for all i, because a single character is always a palindrome of length 1.
  3. Iterate over substring lengths l from 2 to n. For each substring length:

a. Iterate over all possible starting indices i such that i + l - 1 < n.

b. Let j = i + l - 1 be the ending index.

c. If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2, because the matching characters can extend the palindrome in the middle.

d. If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1]), because we must remove either s[i] or s[j] to maximize the palindromic subsequence. 4. After filling the DP table, the longest palindromic subsequence of the entire string is dp[0][n-1]. 5. Compute min_deletions = len(s) - dp[0][n-1]. If min_deletions <= k, return true; otherwise, return false.

Why it works: The DP approach guarantees that for every substring, we correctly compute the longest palindromic subsequence using optimal substructure. By comparing the minimum deletions to k, we correctly determine if the string can be transformed into a palindrome with at most k deletions.

Python Solution

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                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

The implementation first initializes the DP table and sets base cases for single-character substrings. It then iterates over increasing substring lengths, filling the table using the recurrence relation. Finally, it calculates the minimum deletions and compares with k.

Go Solution

func isValidPalindrome(s string, k int) bool {
    n := len(s)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                if length == 2 {
                    dp[i][j] = 2
                } else {
                    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
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go version mirrors the Python implementation. The only notable difference is the explicit handling of slices and the need to define a max helper function. Initialization and iteration follow the same DP logic.

Worked Examples

Example 1: s = "abcdeca", k = 2

i j Substring dp[i][j]
0 0 a 1
1 1 b 1
... ... ... ...
0 6 abcdeca 5

min_deletions = 7 - 5 = 2 <= k, so return true.

Example 2: s = "abbababa", k = 1

i j Substring dp[i][j]
... ... ... ...
0 7 abbababa 7

min_deletions = 8 - 7 = 1 <= k, so return true.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Filling the DP table requires iterating over all substring lengths and start indices, both up to n.
Space O(n^2) The DP table stores results for every substring.

The DP approach is efficient for strings up to length 1000, as the number of operations is around 1 million, which is acceptable.

Test Cases

# Basic examples
assert Solution().isValidPalindrome("abcdeca", 2) == True  # remove 'b' and 'e'
assert Solution().isValidPalindrome("abbababa", 1) == True

# Already a palindrome
assert Solution().isValidPalindrome("racecar", 0) == True

# Requires exactly k deletions
assert Solution().isValidPalindrome("abcdef", 5) == True

# Too many deletions needed
assert Solution().isValidPalindrome("abcdef", 2) == False

# Single character
assert Solution().isValidPalindrome("a", 0) == True

# Empty string
assert Solution().isValidPalindrome("", 0) == True
Test Why
"abcdeca", 2 Valid k-palindrome with exact deletions
"abbababa", 1 Already close to palindrome
"racecar", 0 Already a palindrome, no deletions
"abcdef", 5 Max deletions required
"abcdef", 2 Cannot become palindrome with k=2
"a", 0 Single character edge case
"", 0 Empty string edge case

Edge Cases

One edge case is a string of length 1. Any single character is already a palindrome, so k is irrelevant, and the function should return true. Our DP table handles this because dp[i][i] is set to 1.

Another edge case is an empty string. Although the constraints specify at least one character, handling an empty string gracefully is good practice. The algorithm would return true because `min_deletions = 0