Problem Statement

Given a string str, the task is to find the minimum number of characters to be inserted to convert it to palindrome.Before we go further, let us understand with few examples:

• ab: Number of insertions required is 1 i.e. bab
• aa: Number of insertions required is 0 i.e. aa
• abcd: Number of insertions required is 3 i.e. dcbabcd
• abcda: Number of insertions required is 2 i.e. adcbcda which is same as number of insertions in the substring bcd(Why?).
• abcde: Number of insertions required is 4 i.e. edcbabcde

Problem Link

Minimum insertions to form a palindrome | DP-28 - GeeksforGeeks

Reference Video

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

Approach

Minimum number of deletion in a string s to make it a palindrome =                                                                                   Minimum number of insertion 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)