842. K-Deletion Palindrome
A sign painter wants the word on a board, stored in s, to read the same forwards and backwards. She is allowed to scrape off at most k letters; the remaining letters keep their original order and are not moved.
Return true if, after removing at most k letters, the word can become a palindrome, and false otherwise. An empty or single-letter word counts as a palindrome, and a value of k as large as the word always works.
Aim for time O(n^2) and extra space O(n), where n is the length of s. Trying all subsets of deletions is exponential.
Example 1
- Input:
- s = "tomatoot", k = 3
- Output:
- true
- Explanation:
Deleting the letters m, the second t and the second o from the end leaves the palindrome toaot, so 3 deletions are enough.
Example 2
- Input:
- s = "bananabread", k = 3
- Output:
- false
- Explanation:
The longest palindrome that can be kept is bananab with 7 letters, which needs 4 deletions, one more than allowed.
Constraints
1 ≤ s.length ≤ 1000
s consists of lowercase English letters
0 ≤ k ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)