Valid Palindrome III

Hard
1037.

Valid Palindrome III

Valid Palindrome III is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var isValidPalindrome = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Valid Palindrome III — Solution in Python, Java & C++

Valid Palindrome III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Valid Palindrome III is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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

Hints for Valid Palindrome III

  1. Hint 1

    Whatever you keep must itself be a palindrome — and it is a subsequence of s.

  2. Hint 2

    So the fewest removals equals n minus the length of the longest palindromic subsequence.

  3. Hint 3

    That length is the classic interval DP on s[i..j].

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

  1. Let dp[i][j] be the LPS length of s[i..j], with dp[i][i] = 1.
  2. 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]).
  3. 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

Java

public static boolean isValidPalindrome(String s, int k) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int 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;
}

C++

bool isValidPalindrome(string s, int k) {
    int n = (int) s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) dp[i][j] = (len == 2 ? 0 : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming