Minimum number of deletions in a string to make it a palindrome

Problem Statement

Given a string of size ‘n’. The task is to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome.

Note: The order of characters should be maintained.

Examples :

Input : aebcbda
Output : 2
Remove characters 'e' and 'd'
Resultant string will be 'abcba'
which is a palindromic string

Input : geeksforgeeks
Output : 8

Problem Link

Minimum number of deletions to make a string palindrome - GeeksforGeeks

Reference Video

https://www.youtube.com/watch?v=CFwCCNbRuLY&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=29&ab_channel=AdityaVerma

Approach

Minimum number of deletion in a string s to make it a palindrome = Length of s -                     Length Longest Palindromic Subsequence of string s = length of s -                                    length of LCS(s,reverse(s))

Complexity Analysis

Time and Space Complexity of the above implementation is O(n*n)