Valid Palindrome III

Valid Palindrome III asks a "k-palindrome" question: can we delete at most k characters from a string and have what is left be a palindrome? The clean way to answer it is a classic dynamic-programming quantity — the Longest Palindromic Subsequence (LPS).

The slow way first

The brute-force idea is to try every subset of characters to delete (up to size k) and test whether the remainder is a palindrome. That is exponential — there are far too many subsets to check.

The question to ask: what is the fewest deletions that turns s into a palindrome? If we keep the longest palindromic subsequence and delete everything else, that is provably the minimum. So the whole problem reduces to computing one number, the LPS length.

The idea: keep the longest palindrome inside

If L is the length of the longest palindromic subsequence of s, then the characters we must delete are exactly n - L. So:

s is a k-palindrome ⇔ n - LPS(s) ≤ k.

We compute LPS with a grid. Let dp[i][j] be the LPS of the substring s[i..j]. The recurrence walks outward from each window:

• If the ends match (s[i] == s[j]): wrap them around the best inside, dp[i][j] = dp[i+1][j-1] + 2.
• If they differ: drop one end, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

The base case is the main diagonal: a single character is a palindrome of length 1, so dp[i][i] = 1.

Walk through it

Step through the animation. The string "abca" sits on top; the dp grid fills underneath. We seed the diagonal with 1s, then fill longer windows. Every window where the ends differ stays at 1 — until the full window "abca", whose ends are both a. They match, so dp[0][3] = dp[1][2] + 2 = 3. That top-right cell is LPS = 3. Then n - LPS = 4 - 3 = 1 ≤ k, so the answer is true.

Pseudocode

n = length of s
dp = n x n grid of zeros          # dp[i][j] = LPS of s[i..j]
for i from n-1 down to 0:
    dp[i][i] = 1                  # single char is a palindrome
    for j from i+1 to n-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])
lps = dp[0][n-1]
return n - lps <= k

The Python solution

def is_valid_palindrome(s, k):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            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])
    lps = dp[0][n - 1]
    return n - lps <= k

• dp[i][j] holds the LPS length of the substring s[i..j].
• We iterate i downward so that dp[i+1][...] (a smaller window) is already filled when we need it.
• dp[i][i] = 1 is the base case — every single character is a length-1 palindrome.
• When s[i] == s[j], both ends join the palindrome: take the inner best and add 2.
• When they differ, the best palindrome must skip one end, so we take the larger of the two sub-windows.
• lps = dp[0][n-1] is the answer for the whole string; the final line checks n - lps <= k.

Complexity

We fill each of the n² grid cells in O(1) work, so the running time is O(n²). The grid itself is the O(n²) space (it can be squeezed to O(n) with rolling rows, but the square grid is the clear version).

When this pattern shows up

Practice