609. Valid Palindrome III
Call a string a k-palindrome if it can be turned into a palindrome by deleting at most k of its characters. Deleted characters may come from anywhere; the survivors keep their original order.
You receive a string s of lowercase English letters and an integer k. Return true if s is a k-palindrome and false otherwise.
Example 1:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Deleting 'b' and 'e' leaves "acdca", a palindrome, and that uses only 2 deletions.
Example 2:
Input: s = "abbababa", k = 1
Output: true
Explanation: Deleting the first 'b' leaves "abababa", already a palindrome.
Example 3:
Input: s = "abc", k = 1
Output: false
Explanation: One deletion leaves two distinct letters ("bc", "ac", or "ab") — none is a palindrome, and "abc" itself is not one either.
Constraints:
- 1 ≤ s.length ≤ 1000
- 1 ≤ k ≤ s.length
- s consists of lowercase English letters only.
Hints:
"Can it be done with at most k deletions?" is really "what is the *minimum* number of deletions that makes s a palindrome?" Compute that number once and compare it to k.
Look at the two ends of an interval. If s[i] == s[j], neither end needs to go — recurse on the inside. If they differ, one of the two ends must be deleted; try both and take the cheaper. That recurrence has only O(n²) distinct (i, j) states, so memoize it or fill a table bottom-up.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abcdeca", k = 2
Expected output: true