HardStringsAI interview only
Valid Palindrome III
Asked atmetaamazongoogle
01 · Problem
Given a string s and an integer k, return true if you can delete at most k characters from s (from any positions) so that the remaining characters, kept in their original order, form a palindrome. Otherwise return false.
Deleting zero characters is allowed, so a string that is already a palindrome always returns true.
02 · Examples
Example 01
Input
s = "racxecar", k = 1
Output
true
Remove the "x" to get "racecar".
Example 02
Input
s = "abcdef", k = 3
Output
false
All letters differ, so the longest palindromic subsequence has length 1 and 5 removals would be needed, more than k = 3.
Example 03
Input
s = "abccxba", k = 2
Output
true
Removing one "c" and the "x" gives "abcba", using exactly 2 removals.
03 · Constraints
- 011 <= s.length <= 1000
- 02s consists only of lowercase English letters
- 031 <= k <= s.length
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.