โ† Morgan Stanley questions
CodingReported in a candidate post, Oct 2023

Minimum Deletions to Make String Palindrome

Filed under Morgan Stanley

Free read 3 of 3

Understand 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

  1. Understand that the minimum deletions to make a string a palindrome is equivalent to `Length of string - Length of Longest Palindromic Subsequence (LPS)`.

Solution

O(n^2) time, O(n^2) space

Python
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.