valid-palindrome-iii

< Previous 　　　　　　　　　　　　　　　　 Next >

1216. Valid Palindrome III (Hard)

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

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.

 

Constraints:

• 1 <= s.length <= 1000
• s has only lowercase English letters.
• 1 <= k <= s.length

Related Topics

[String] [Dynamic Programming]

Hints

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.