Form a Palindrome Geeks For Geeks

 Question Link:

https://practice.geeksforgeeks.org/problems/form-a-palindrome2544/1

It is also the problem of the day for 24-03-2022.

Solution:

int findMinInsertions(String s1){

        int n=s1.length();

        StringBuilder sb=new StringBuilder(s1);

        String s2=sb.reverse().toString();

        

    int m=s2.length();

    int p=cal(s1,s2,n,m);

    //System.out.println(p);

    return p;

    }

public int call(String s1, String s2, int n , int m){

    int t[][]=new int[n+1][m+1];

    for(int i=0;i<1;i++){

        for(int j=0;j<1;j++){

                if(i==j){

                        t[i][j]=0;

                }

        }

    }

for(int i=0;i<1;i++){

        for(int j=0;j<1;j++){

               if(s1.charAt(i-1)==s2.charAt(j-1)){

                        t[i][j]=1+t[i-1][j-1];

                }

                else{

                        t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);

                    }

        }

    }

int a=t[n][m];

//int del=n-a;(If number of character deleted is asked then del is answer)

int ins=m-a;

return ins;

}

Time Complexity:O(N*M)[N == s.length() && M== s.length()][GFG Time:0.2/1.4]

Space Complexity:O(1)[String is given]

Auxilaary Space:O(N*M)[A 2d matrix of n*m]

Approach Used:

Approach of Dynamic Programming is Used.

For making the string palindrome by adding characters we need to find LCS.

LCS is the Longest Common Subsequence.

It is calculated between two strings and it gives us the value of common characters length between those two strings.

So for LCS, we require two strings, and one string is given to us already ie s1.

Now we want another string that will be compatible in making the first string palindrome so the best match of the second string will be the reverse of the first string.

It is so because when you will compare characters of both strings you will get common characters ie LCS which ultimately means that those characters should be present in the given string to make it palindrome or that length should be preserved to make it palindrome when you will either add or delete characters. 

It also means the shortest range in the given string which will remain palindrome throughout and will not be affected by any deletion. If you want to delete characters also then up to that length you can delete but once that sequence is there it ensures it is a palindrome.

Further addition of characters in LCS may develop many palindromic strings and which will have more characters and hence increase LCS value too. For that only we use Integer.max function to find out the maximum length possible for LCS.

In t matrix t[i][j]=0 if(i==0 || j==0) because it means s1.length()==0 or  s2.length()==0 so for null strings lcs will also be 0.Here s2 is reverse of s1 so if s1 is nnull s2 willl be null ulitmately and vice versa.

So In a gist.

We find out LCS firest by comparing s1 with s2(reverse of s1)

After finding out LCS we have a value of common length characters between two strings.

Now we will find out the number of characters to be inserted or deleted, which will be simply making 

string length == LCS length by performing deletions of (string length-LCS)characters

or making 

string length==stringlength+(string length-LCS) by performing insertion of (string length-LCS length)characters.

(Since LCS is a part of string so it will always be less than or equal to string.length().)

Total Test Cases:70

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"