Minimum Deletions to Make String Palindrome
Filed under Morgan Stanley
Free read 3 of 3Understand that the minimum deletions to make a string a palindrome is equivalent to `Length of string - Length of Longest Palindromic Subsequence (LPS)`.
The question
Given a string, find the minimum number of deletions required to make it a palindrome. Note that the character order can be preserved, but characters can be deleted.
Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Examples
- Input
- s = "abceba"
- Output
- 1
- Why
- Remove 'c' to get "abeba", which is a palindrome.
Approach
Understand that the minimum deletions to make a string a palindrome is equivalent to `Length of string - Length of Longest Palindromic Subsequence (LPS)`.
Generate all possible subsequences, check if each is a palindrome, and find the longest one, taking exponential time.
Use Dynamic Programming to find the LPS of the string. Alternatively, find the Longest Common Subsequence (LCS) between the string and its reverse.
String of length 1, or string with all identical characters.
Solution
O(n^2) time, O(n^2) space
def minDeletionsToPalindrome(s):
rev = s[::-1]
n = len(s)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if s[i-1] == rev[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return n - dp[n][n]
Tips
- What they are testing: Test with already palindromic strings, single character strings, and strings with no common palindromic subsequences.
- Common mistake: Confusing minimum deletions with minimum insertions or trying a greedy approach instead of recognizing it relates to Longest Palindromic Subsequence.
Related Morgan Stanley questions
Collected from public candidate posts and coding forums. Updated Nov 2026.