https://stackoverflow.

com/questions/6184869/what-is-the-difference-between-memoization
%20Programming,solving%20the%20problem%20bottom%2Dup .

https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/?ref=rp
https://www.techiedelight.com/longest-common-subsequence/

https://www.techiedelight.com/longest-common-subsequence-lcs-space-optimized-version/

Q) Basic Concept of Longest Common Subsequence (Dynamic Programming)

Ex1) Recursive Implementation(Naive)

int lcs (char* str1,char* str2,int m,int n)
{
    // Base Case :- If We have reached the end of either string
    if( (m==0) || (n==0) )
        return 0;

    // If Last character of str1,str2 matches
    if(str1[m-1] == str1[n-1])
        return 1 + lcs(str1,str2,m-1,n-1);

    // Else If last character of str1,str2 does not match
    return max(lcs(str1,str2,m,n-1),lcs(str1,str2,m-1,n));
}

1) Time Complexity:-
 Time complexity of the above naive recursive approach is O(2 m + n ) in the worst case
 Worst Case happens when all characters of str1 and str2 mismatch
 i.e. Worst Case occurs  When length of Longest Common Subsequence is 0.
 Each Recursive call will end up in 2 recursive calls

2) If we draw the Complete Recursion Tree

 We can see that there are many subproblems which are solved again and again.
 So this problem has Overlapping Substructure property
 Recomputation of same subproblems can be avoided by either using Memoization or Tab

3) A Problem is said to have overlapping subproblems property :-

 If the recursive algorithm for the problem solves the same subproblem over and
over again rather than generating new subproblems
4) Let us consider the recursion tree for 2 strings of length 6,8 whose LCS is 0

 m = 6,n = 8………
 In the Partial Recursion Tree Diagram lcs(str1,str2,6,8)  (6,8)
 Similarly lcs(str1,str2,5,8) represented as (5,8)
 As we can see that the same subproblems(highlighted in the same color) are getting
computed again and again

4) Optimal Substructure Property 

 i.e main problem can be solved using solutions to the subproblems

5) Since the longest common subsequence problem has

 Optimal substructure property and Overlapping Substructure property
 This problem can be solved either by memoization or Dynamic Programming
 We Know Memoization  Top-Down Approach
 Dynamic Programming  Bottom-Up Approach

https://www.techiedelight.com/longest-common-subsequence-of-k-sequences/

Q) Longest Common Subsequence of more than 2 strings

1) Previously We had seen how to find LCS b/w 2 strings str1,str2

 Now we’ll be discussing how to find length of LCS b/w 3 strings str1,str2,str3
 And of course this concept can be generalized to handle more than 3 strings as well
Ex1) Naïve Recursive Approach
// Function to return maximum of three integers
int max(int a,int b,int c)
{
    return max(max(a,b),c);
}

int lcs(string str1,string str2,string str3,int len1,int len2,int len3)
{
    // Base Case :- If we have reached the end of either string
    if ( (len1 == 0)||(len2==0)||(len3==0) )
        return 0;

    // if last character of str1,str2,str3 matches
    if( (str1[len1-1]==str2[len2-1]) && (str2[len1-1]==str3[len3-1]) )
        return 1 + lcs(str1,str2,str3,len1-1,len2-1,len3-1);

    // else if last character of X, Y, Z don't match
    return max( lcs(str1,str2,str3,len1-1,len2,len3),
                lcs(str1,str2,str3,len1,len2-1,len3),
                lcs(str1,str2,str3,len1,len2,len3-1) );
}

Ex2) Memoized Version of lcs algo

 Using unordered_map to store the computed subproblems

https://www.techiedelight.com/find-longest-common-prefix-lcp-strings/

https://www.geeksforgeeks.org/longest-common-prefix-using-divide-and-conquer-algorithm/?r

Q) Longest Common Prefix b/w 2 and more Strings

Ex1) Finding Longest Common Prefix by word by word matching method

Concept:-
1) First write a function to find the longest commmon prefix b/w 2 strings

2) We’ll see that the Longest Common Prefix b/w 3 or more strings holds the associative prop

3) LCP(str1,str2,str3,str4) = LCP(LCP(str1,str2),str3,str4) = LCP(result1,str3,str4)

= LCP(LCP(result1,str3),str4) = LCP(result2,str4) = answer

4) The above procedure can be extended for n number of strings also

5) In the above example:-

 result1 = LCP b/w str1,str2
 result2 = LCP b/w
 // Function to find the longest common prefix between string longestCommonPrefix(
// 2 strings str1,str2  {
string longestCommonPrefixTwo(string str1,string str2)     int i;
{     string answer = arr[0];
    int i,j;
    int len1 = str1.length();     for(i=1;i<n;i++)
    int len2 = str2.length();     {
    string result;         answer = longestCom
    }
    for(i=0,j=0;i<len1,j<len2;i++,j++)     return answer;  
    { }
        if(str1[i] != str2[j])
            break;
        
        result.push_back(str1[i]);
    }
    return result;
}

1) Time Complexity = O(n*m)

 n = length of the string arr[] = No. of strings in the string array.
 m = length of the largest prefix string .

2) Space Complexity = O(m)

 bcoz a result[] array is used to store the largest prefix string.

3) In the above problem:-

 arr[] = String array containg strings.
 n = no. of Strings in arr[] = Lenth of arr[].
 answer = The final answer = i.e the longest_common_prefix of the strings in the array.

Ex2) A Good Way of finding common Prefix b/w 2 strings

 without using an extra array to store the result
 We’ll use a C++ string function

string longestCommonPrefix2(string str1,string str2)
{
    int i=0,j=0;
    int len1 = str1.length();
    int len2 = str2.length();

    while((i<len1) && (j<len2))
    {
        if(str1[i] != str2[j])
            break;
        i++,j++;
    }
    return str1.substr(0,i);// Or return str2.substr(0,i);
}

Q) KMP Algo

1) Pattern = a b c d a b c
 Prefix = a,ab,abc,abcd
 Suffix = c,

1) oni
 Prefix = o,on
 Suffix = i,ni
 In other words , We cant take entire word as the Prefix or Suffix.

Ex1) Working (In Detail) (The Preprocessing Part)

Ex1) Working (In Detail) (The KMP Algo)

1) str = “AAAAABAAABA”
patt = “AAAA” 2) i=5,j=3
 Hence lps = {0, 1, 2, 3}  str = “AAAAABAAA
 n = length of string  patt = “AAAA”
 m = length of pattern.  str[i] , patt[j] don’t m
 Change only j.
2) i=0,j=0  j = lps[j-1] = lps[3-1
 str = “AAAAABAAABA”
 patt = “AAAA” 2) i=5,j=2
 str[i] , patt[j] match  Do i++,j++  str = “AAAAABAAA
 patt = “AAAA”
2) i=1,j=1  str[i] , patt[j] don’t m
 str = “AAAAABAAABA”  Change only j.
 patt = “AAAA”  j = lps[j-1] = lps[2-1
 str[i] , patt[j] match  Do i++,j++
2) i=5,j=1
2) i=2,j=2  str = “AAAAABAAA
 str = “AAAAABAAABA”  patt = “AAAA”
 patt = “AAAA”  str[i] , patt[j] don’t m
 str[i] , patt[j] match  Do i++,j++  Change only j.
 j = lps[1-1] = lps[1-1
2) i=3,j=3
 str = “AAAAABAAABA” 2) i=5,j=0
 patt = “AAAA”  str = “AAAAABAAA
 str[i] , patt[j] match  Do i++,j++  patt = “AAAA”
 str[i] , patt[j] don’t m
2) i=4,j=4  Hence we do i++.
 str = “AAAAABAAABA”
 patt = “AAAA” 2) i=6,j=0
 Now j == m  A Pattern is found.  str = “AAAAABAAA
 Hence reset j  patt = “AAAA”
 j = lps[j-1] = lps[4-1] = lps[3] = 3.  str[i] , patt[j] match

2) i=4,j=3 2) i=7,j=1
 str = “AAAAABAAABA”  str = “AAAAABA AA
 patt = “AAAA”  patt = “AAAA”
 str[i] , patt[j] match  Do i++,j++  str[i] , patt[j] match

2) i=5,j=4 Continue like this.

 str = “AAAAABAAABA”
 patt = “AAAA”
 Now j == m == 4  A Pattern is found.
 Hence reset j
 j = lps[j-1] = lps[4-1] = lps[3] = 3.

Q) Check if String str1 is a subsequence of String str2

Ex1) Iterative Approach

https://www.techiedelight.com/find-lexicographic-permutations-string/

Q) Lexicographical permutations of a String

Ex4) Using Dynamic Programming to solve the Problem

1) Create a table table[m+1][n+1]

2)

Fill the 0 t h row,0 t h column of the table[][] with zeroes

3) Then Fill the remaing cells of the table using the Formula:-
 table(i,j) = 1 + table(i-1,j-1) …….If str1[i-1] == str2[j-1]
 table(i,j) = max( table(i-1,j) , table(i,j-1) )……Otherwise
 table(i,j) = 0……………………………………..If i,j = 0

4) Ok So Folks….Let’s construct the table

 Suppose str1 = “XMJYAUZ”  m = 7
 Suppose str2 = “MZJAWXU”  n = 7
 In rows,Write the characters of str1……In columns,Write the characters of str2

(0) MN(1) Z(2) J(3) A(4) W(5) X(6) U(7)

(0) 0 0 0 0 0 0 0 0
X(1) 0
M(2) 0
J(3) 0
Y(4) 0
A(5) 0
U(6) 0
Z(7) 0

5) In this table:-
 Value in table[i][j] shows the length of LCS formed b/w str1[0..i-1] and str2[0..j-1]
 So Value in table[m][n] shows the length of LCS formed b/w str1[0..m-1] and str2[0

Ex5) Dynamic Programming Soln to find length of LCS

 Using 2D array to avoid recomputation of computed subproblems
 Bottom-Up Approach

// Function to find length of Longest Common Subsequence
// in str1[0..m-1] and str2[0..n-1]
int LCSLength(string str1, string str2,int m,int n)
{ 
    // lookup table stores solution to already computed sub-problems
    // i.e. lookup[i][j] stores the length of LCS of b/w strings
    // str1[0..i-1] and str2[0..j-1]
    int lookup[m + 1][n + 1];
    int i,j;
 
    // first column of the lookup table will be all 0
    for (i = 0; i <= m; i++)
        lookup[i][0] = 0;
 
    // first row of the lookup table will be all 0
    for (j = 0; j <= n; j++)
        lookup[0][j] = 0;
 
    // fill the lookup table in bottom-up manner
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++)
        {
            // if current character of X and Y matches
            if (str1[i - 1] == str2[j - 1])
                lookup[i][j] = 1 + lookup[i - 1][j - 1];
 
            // else if current character of X and Y don't match
            else
                lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]);
        }
    }
 
    // length of LCS b/w str1,str2 will be last entry in the lookup table
    return lookup[m][n];
}

1) Time Complexity = O(mn)

2) Space Complexity = O(mn)

 2D array of dimensions (m+1 * n+1) used

https://www.geeksforgeeks.org/minimum-insertions-to-form-a-palindrome-dp-28/

Q) Minimum no. of insertions to make a String Palindrome

Q) Longest common Prefix in an Array of Strings