Is Valid Palindrome III easy or hard?

Valid Palindrome III is classified as a hard problem because it requires recognizing the relationship between deletions and the longest palindromic subsequence. Candidates must design a correct dynamic programming state and handle O(n²) transitions.

Valid Palindrome III Python/Java solution

Most implementations build a dynamic programming table of size n × n. Python, Java, C++, Go, TypeScript, and Rust versions follow the same logic: compute the longest palindromic subsequence or minimum deletions and compare the result with k.

How to solve Valid Palindrome III in O(n)?

An exact solution cannot be achieved in O(n) for the general case because the algorithm must evaluate relationships between many character pairs. The best practical solution uses dynamic programming with O(n²) time to compute the longest palindromic subsequence or minimum deletions.

What is the best approach for Valid Palindrome III?

The most common solution uses dynamic programming to compute the Longest Palindromic Subsequence (LPS). If the string length is n and the LPS length is L, then the minimum deletions required is n − L. The string is a valid k‑palindrome if n − L ≤ k. This approach runs in O(n²) time.

Is Valid Palindrome III asked at Google/Amazon/Meta?

Palindrome transformation and subsequence dynamic programming problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving minimum deletions, longest palindromic subsequence, or edit-style DP are common interview patterns.

What data structure is used in Valid Palindrome III?

The primary structure is a 2D dynamic programming table where dp[i][j] stores either the longest common subsequence length or the minimum deletions for substring s[i..j]. The input itself is processed as a string, and optimized versions use rolling arrays.

What is the time complexity of Valid Palindrome III?

The optimal dynamic programming solutions run in O(n²) time because they evaluate all substring pairs or compute LCS between the string and its reverse. Space complexity is typically O(n²), though it can be optimized to O(n) with rolling arrays.

Description Hints 4 Solution Video 16:01

1216. Valid Palindrome III

Hard49.2% acceptance3 companiesPremium elsewhere, free here

Given a string s and an integer k, return true if s is a k-palindrome.

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

Example 1:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

Constraints:

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

Asked at 3 companies

Meta Tiktok Amazon

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

Can you reduce this problem to a classic problem?

Hint 2

The problem is equivalent to finding any palindromic subsequence of length at least N-K where N is the length of the string.

Hint 3

Try to find the longest palindromic subsequence.

Hint 4

Use DP to do that.

16:01

Still stuck?Read the written solution, or watch a walkthrough.

Open solution