Minimum Deletions to Make Palindrome
Medium · Dynamic Programming · String · Dynamic Programming
Problem
You are given a string s. You may delete characters from any positions; the characters that remain keep their order.
Return the minimum number of deletions needed so that the remaining string is a palindrome (reads the same forwards and backwards). A single character is a palindrome, so the answer is always less than len(s).
Examples
Input: s = "racecbar" Output: 1
Deleting the "b" leaves "racecar".
Input: s = "abcdcxba" Output: 1
Keep "abcdcba" by deleting "x", one deletion.
Input: s = "noon" Output: 0
Nothing needs to go.
Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Approaches
- Recursion on the two ends — time O(2^n), space O(n)
Follow-up
Since the kept characters form a palindromic subsequence, the answer is n - LPS(s), and LPS(s) equals the longest common subsequence of s and its reverse. The interval table also answers every substring at once, so a list of queries "fewest deletions for s[l..r]" costs O(1) each after O(n²) preprocessing.
Related problems
Start free on Cariara · Coding problems · System design studio
