JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

DPL29 Minimum Insertions to Make String Palindrome

A palindromic string is a string that is the same as its reverse. For example: “nitin” is a palindromic string. Now the question states that we are given a string, we need to find the minimum insertions that we can make in that string to make it a palindrome. We insert the any character any where that is the Important Point

+

This Problem is the Extended Versiojn of the DPL25 & DPL28

If we Go with the BruteForce Approch then what we do is, I just put the String + reverse(String) that is the My Answer.

Number of Operation is len(S1)

But this is Not the Question, Our Question is Minimum Operation Required not the Maximum Operation Required

Approch

We need to find the minimum insertions required to make a string palindrome. Let us keep the “minimum” criteria aside and think, how can we make any given string palindrome by inserting characters?

To minimize the insertions, we will first try to refrain from adding those characters again which are already making the given string palindrome. Track the Longest Plandromic portion of the String

So what we do is we just Double the match string portion of the string and feed between the every char of the Longest Palindromic Portion first part feed as it is and feed second part in the Reverse Order for the left and right Match

Just Take the Example of the "codingninjas the Longest Palindromic Portion is the "ingni" and we have remaining portion are not match.

Follow the Same Approch Again Dnouble the Non Match Portion of the String, first feed as itis and Second put in the Reverse order for the Match

So what we Observed in this Entire Process Excluding the Longest Palindromic Portion we Double the Remaining. part of the String So we can Say that, len(S) - Longest Palindromic Subsequence is my Answer.

Now Remaining Entire 👇 Process will Be Same As Like in DPL28

Let's Try To Conncet this Problem with the DPL25

No the Question is Why we Want to Connect this Question with the DLP25? becouse we want to creat the problrm patters.

If We Closely Observed then this Problem is the Replica of the DPL25 becouse Our task is Find the Longest Palindromic Subsequence and what is the Longest Palindromic Subsequence? those String that equla to the its Reverse String that is Palindromic String.

Now if we go with the DPL25 then we required the 2 string but here is the we have only one string(S1) so what we do is Reverse the String(S2).

Why we Wnat to Reverse the String?
Becouse we Try to Convert this Problem into the DPL25, After Converting the Our Given String into the S1 and S2

S1: String

S2: reverse(String)

if we Observed very carefully then this is nothing but this is the Longest Common Subsequence in the Both String.

Longest Common Subsequence is the the Our Ans, becouse we know that the Defination of the Palindromic String we have S1 and reverse(S1) if Some part of the both String is Common that is the Our ans.

Thst's why we try to Convert this Problem into the DPL25

Now Remaining Entire 👇 Process will Be Same As Like in DPL25

In This Part we Discuss about DP on String and we form the

Comparision

edit/delet

Replacement

VVVV Imp Always Remember For a string of length n, the number of subsequences will be 2^n.
if we want to generate of find all the possible Subsequences then we have 2 different Approch.

Power Set

Recursion

Algorithm / Intuition If We Talk About the Brute Force Approch then, We are given two strings, S1, and S2 (suppose of same length n), the simplest approach will be to generate all the subsequences and store them, then manually find out the longest common subsequence.

This Approach will give us the correct answer but to generate all the subsequences, we will require exponential ( 2^n ) time. Therefore we will try some other approaches.

Now here we go with the Dynamic Programming and Recursion To generate all subsequences we will use recursion and in the recursive logic

Recursice Approch

Steps to form the Recursive Solution
Step 1: Express the problem in terms of indexes.

Here Have a 2 String String1 & String2 thats why we required the 2 indexes foe the recursion Solution index1 & index2

A single variable can’t express both the strings at the same time, so we will use two variables ind1 and ind2. They mean that we are considering string S1 from index 0 ind1 and string S2 from index 0 to S2. So our recursive function will look like this

Step 2: Try out all possible choices at a given index.
Intuition for Recursive Logic

In the function f(ind1,ind2), ind1 and ind2 are representing two characters from strings S1 and S2 respectively. For example:

Now, there can be two possibilities

if(S1[ind1] == S2[ind2]) as in the figure below. In this case this common element will represent a unit length common subsequence, so we can say that we have found one character and we can shrink both the strings by 1 to find the longest common subsequence in the remaining pair of strings.

if(S1[ind1] != S2[ind2]) as in the figure given below. In this case we know that the current characters represented by ind1 and ind 2 will be different. So, we need to compare the ind1 character with shrunk S2 and ind2 with shrunk S1. But how do we make this comparison ? If we make a single recursive call as we did above to f(ind1-1,ind2-1), we may lose some characters of the subsequence. Therefore we make two recursive calls: one to f(ind1,ind2-1) (shrinking only S1) and one to f(ind1-1,ind2) (shrinking only S2). Then when we return max of both the calls.

Step 3: Return the maximum of Pick and notPick

In the first case, we have only one choice but in the second case we have two choices, as we have to return the longest common subsequences, we will return the maximum of both the choices in the second case.

Base Case
if S1[ind1] != S2[ind2]

We will make a call to function(0-1,1), i.e function(-1,1) but a negative index simply means that there are no more indexes to be explored, so we simply return 0. Same is the case when S1[ind1]==S2[ind2]

If (ind1 < 0 || ind2 < 0 ) return 0.

The final pseudocode after steps 1, 2, and 3

Recursion Tree

Time & Space Complexity

Time Complexity: O(2^N)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Steps to convert Recursive code to memoization solution:

Create a dp array of size [N][M] where N and M are lengths of S1 and S2 respectively. It will store all the possible different states that our recursive function will take.

We initialize the dp array to -1.

Whenever we want to find the answer of particular parameters (say f(ind1,ind2)), we first check whether the answer is already calculated using the dp array(i.e dp[ind1][ind2]!= -1 ). If yes, simply return the value from the dp array.

If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[ind1][ind2] to the solution we get.

Time & Space Complexity

Time Complexity:O(N*M)
Reason: There are N*M states therefore at max ‘N*M’ new problems will be solved.
Space Complexity: O(N*M) + O(N+M)
Reason: We are using an auxiliary recursion stack space(O(N+M)) (see the recursive tree, in the worst case, we will go till N+M calls at a time) and a 2D array ( O(N*M)).

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

In Tabulation Approch We Just Creat a DP Array Same as Memoization and Simply Convert the Recurance Relation into the form of the Looping

Steps to convert Recursive Solution to Tabulation one.

To convert the memoization approach to a tabulation one, create a dp array with the same size as done in memoization. We can initialize it as 0.

Initialization: Shifting of indexes

In the recursive logic, we set the base case to if(ind1 < 0 || ind2 < 0) but we can’t set the dp array’s index to -1. Therefore a hack for this issue is to shift every index by 1 towards the right.

Therefore, now the base case will be if(ind1==0 || ind2==0).

Similarly, we will implement the recursive code by keeping in mind the shifting of indexes, therefore S1[ind1] will be converted to S1[ind1-1]. Same for others.

At last we will print dp[N][M] as our answer.

Time & Space Complexity

Time Complexity: O(N*M)
Reason:There are 2 nested loops
Space Complexity: O(N*M)
Reason: We are using an external array of size ‘N*M)’. Stack Space is eliminated.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: dp[ind1-1][ ], dp[ind][ ] for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

Golden Rule

If we required only Prev row and Prev Collom then definetly we can Space Optimized

So we are not required to contain an entire array, we can simply have two rows prev and cur where prev corresponds to dp[ind-1] and cur to dp[ind].

After declaring prev and cur, replace dp[ind-1] to prev and dp[ind] with cur and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.

Time & Space Complexity

Time Complexity: O(N*M)
Reason: There are three 2 nested loops
Space Complexity: O(M)
Reason: We are using an external array of size ‘M+1’ to store only two rows.