Problems you can solve using LCS (Longest Common Subsequence)

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

class Solution {
public:
    int f(int i, int j,string text1, string text2){
        // base constion - if indexes are less than zero return 0
        if (i < 0 || j < 0) return 0;
        // Take and not take cases for statndard dp problems-
        // take - increase the count if last index of both the strings are matching and call the function with reduced indexes.
        if (text1[i] == text2[j])
            return 1 + f(i-1,j-1,text1,text2);
        
        // not take - In this we will check two possible conditions  - 
    	// first we will check the first reduced index with second index if they match it will return the 1 and if not it will keep checking
    	// same thing this will do for the other case  - it will return the max of these functions
        return max(f(i-1,j,text1,text2),f(i,j-1,text1,text2));
    }
public:
    int longestCommonSubsequence(string text1, string text2) {
		// create 2 indexes and keep them at the end of strings.
        int i = text1.size()-1;
        int j = text2.size()-1;
        return f(i,j,text1,text2);
        
    }
};

class Solution{
public:
	// create the LCS function takes indexes, strings, and dp vector
​    int f(int i, int j,string &text1, string &text2,vector<vector<int>>& dp){
		// base constion - if indexes are less than zero return 0
​        if (i < 0 || j < 0) return 0;
		
    	// save the generated values in dp vector
​        if (dp[i][j] != -1) return dp[i][j];
		
    	// take - increase the count if last index of both the strings are matching and call the function with reduced indexes.
​        if (text1[i] == text2[j])
​            return dp[i][j] = 1 + f(i-1,j-1,text1,text2,dp);
    
		// not take - In this we will check two possible conditions  - 
    	// first we will check the first reduced index with second index if they match it will return the 1 and if not it will keep checking
    	// same thing this will do for the other case  - it will return the max of these functions
    	// then we silmply save the result in vector
​        return dp[i][j] = max(f(i-1,j,text1,text2,dp),f(i,j-1,text1,text2,dp));

​    }

public:

​    int longestCommonSubsequence(string text1, string text2) {
		// create 2 indexes and keep them at the end of strings
​        int i = text1.size()-1;
​        int j = text2.size()-1;
		
    	// Create a 2d vector to store the generated values
​        vector<vector<int>>dp(i+1,vector<int>(j+1,-1));
		// return the LCS
​        return f(i,j,text1,text2,dp);
​    }

};

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // take the string size
        int m = text1.size();
        int n = text2.size();
        
        // declare the dp vector with +1 sizes.
        vector<vector<int>>dp(m+1,vector<int>(n+1,-1));
        
        // base consition - fill the first row and first column of dp vector with 0. 
        for (int i=0; i <= m; i++) dp[i][0] = 0;
        for (int j=0; j <= n; j++) dp[0][j] = 0;
        
        // Loop through strings with index 1 to create the matrix dp and check the i-1th and j-1 th index whether they are mactching or not.
        for (int i =1; i <= m; i++){
            for (int j=1; j <= n; j++){
                if (text1[i-1] == text2[j-1])
                    // if they are matching then go to the prev row and prev col as we have already taken the curr row/col.
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    // if this didn't match then simply trace back that where this number is coming from - we will simply took the max of prev row and prev col and try to match the sequence
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        // return the stored result.
        return dp[m][n];
    }
};

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

class Solution {
public:
    // LCS.
    int lcs(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,-1));
        for (int i=0; i <= m; i++) dp[i][0] = 0;
        for (int j=0; j <= n; j++) dp[0][j] = 0;
        for (int i =1; i <= m; i++){
            for (int j=1; j <= n; j++){
                if (text1[i-1] == text2[j-1])
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

            }
            
        }
        return dp[m][n];
        
    }
    int longestPalindromeSubseq(string s) {
        // take a copy of the string and reverse it
        string t = s;
        reverse(t.begin(),t.end());
        // It will simply match the palindrmic subsequence given string s and reversed string t. 
        return lcs(s,t);
        
    }
};

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

class Solution {
public:
    // LCS code
    int lcs(string& text1, string& text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,-1));
        for (int i=0; i <= m; i++) dp[i][0] = 0;
        for (int j=0; j <= n; j++) dp[0][j] = 0;
        for (int i =1; i <= m; i++){
            for (int j=1; j <= n; j++){
                if (text1[i-1] == text2[j-1])
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
        
    }
    // find longest Palindrome.
    int longestPalindromeSubseq(string& s) {
        string t = s;
        reverse(t.begin(),t.end());
        return lcs(s,t);
        
    }
public:
    int minInsertions(string s) {
        // return the size - palindromic subsequence
        return s.size() - longestPalindromeSubseq(s);
        
    }
};

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        // LCS
        int m = str1.size();
        int n = str2.size();
        int dp[m+1][n+1];
        for (int i=0; i <= m; i++) dp[i][0] = 0;
        for (int j=0; j <= n; j++) dp[0][j] = 0;
        for (int i =1; i <= m; i++){
            for (int j=1; j <= n; j++){
                if (str1[i-1] == str2[j-1])
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }               
        }
        
		// Here we have to return the string array 
        string ans = "";
        
        // As our pointers are at the last position (right of the string) at str.size()
        // so as a condition we can say when we hit 0 we will terminate
        while (m > 0 && n > 0){
            
            // if last index matched 
            if (str1[m-1] == str2[n-1]){
                 ans += str1[m-1];
                 m--;
                 n--;
            }
            // here we have two case whne there is no match
            // we have to check both side whether m-1 matches with n or n-1 matches with m in recursive way.
            // but for tabulation, we need to trace back the cur value with respect to m-1 and n-1
            else if (dp[m-1][n] > dp[m][n-1]){
                ans += str1[m-1];
                m--;
            }
            else{
                ans += str2[n-1];
                n--;
            }

        }
        // as of now we have reached to the end or 0 in either row or in column.
        // so we will check if there are any elements we will simply add these to our string array.
        while (m > 0){
            ans += str1[m-1];
            m--;
        }
        while (n > 0){
            ans += str2[n-1];
            n--;
        }
		// as we are iterating from last index and adding the strings.
        // simply reverse the result string and return.
        reverse(ans.begin(),ans.end());
        return ans;    
    }
};