Valid Palindrome III — Hard Problem & Solution

A string is k-palindrome if it can be turned into a palindrome by removing at most k characters. Return whether s is k-palindrome.

Difficulty: Hard
Topics: Strings, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is k-palindrome if it can be turned into a palindrome by removing at most k characters.

Return whether s is k-palindrome.

Example 1

Input: s = "codekairo", k = 6
Output: true
Explanation: `odo` survives — six of the nine characters come out.

Example 2

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove `b` and `e` to leave `acdca`.

Example 3

Input: s = "codekairo", k = 5
Output: false
Explanation: No palindromic subsequence is longer than 3, so five removals are not enough.

Constraints

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

How to solve Valid Palindrome III

The characters you keep form a palindromic subsequence, so the minimum number of removals is n - LPS(s). Compute the longest palindromic subsequence with the standard interval DP and compare.

Approach

Let dp[i][j] be the LPS length of s[i..j], with dp[i][i] = 1.
For increasing lengths: if s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
Return n - dp[0][n-1] <= k.

Why it works

Reframing "remove at most k" as "keep at least n − k" is what turns a search over deletion sets into a single optimisation — and what you keep is exactly a palindromic subsequence, so LPS is the right quantity. The DP itself is the usual one, with the one trap that a length-2 interval with equal ends has no inner interval, so dp[i+1][j-1] must be read as 0 there rather than from an inverted range.

Complexity

Time — O(n²)
Space — O(n²), reducible to O(n) with a rolling row

Pitfalls

A palindromic subsequence — the kept characters need not be contiguous.
At len == 2 the inner interval is empty; reading dp[i+1][j-1] out of order gives garbage in some implementations.
LPS on s equals the LCS of s with its reverse, which is the same O(n²) either way.

Reference solution

Python

def isValidPalindrome(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] = (0 if length == 2 else 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

JavaScript

var isValidPalindrome = function(s, k) {
    var n = s.length, i, j;
    var dp = [];
    for (i = 0; i < n; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        dp.push(row);
    }
    for (i = 0; i < n; i++) dp[i][i] = 1;
    for (var len = 2; len <= n; len++) {
        for (i = 0; i + len - 1 < n; i++) {
            j = i + len - 1;
            if (s.charAt(i) === s.charAt(j)) dp[i][j] = (len === 2 ? 0 : dp[i + 1][j - 1]) + 2;
            else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return n - dp[0][n - 1] <= k;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue