Q: Given two strings str1 and str2, the task is to find the length of the shortest string that has both str1 and str2 as subsequences.
Eg str1 = "geek", str2 = "eke"
O/P : 5 as the string "geeke" contains both "geek" and "eke" as subsequences

• Now 1 way is simply adding both strings i.e "geekeke" (length=7)
• This string has both "geek" and "eke" as subsequences
• but this is not the shortest since "geeke" also has both "geek" and "eke" as subsequences
• One thing to note here is that LCS here is "ek" and actually we added "ek" twice in the "geekeke"
• so removing it once will serve us the purpose
• Once we find LCS, we insert characters of both strings in order and we get "geeke" So we can simply find the length of the SCS as :
• So length of the SCS = length of string 1 + length of string 2 - LCS

int LCS(string X, string Y) {
        
        int m=X.length();
        int n=Y.length();
        int dp[m+1][n+1];
        
        // initialization
        for(int i=0;i<=m;i++)
            dp[i][0]=0;   // Eg LCS of "abc" & "" = 0
        for(int j=0;j<=n;j++)
            dp[0][j]=0;   // Eg LCS of "" & "abc" = 0
        
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(X[i-1]==Y[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 SCS(string X, string Y, int m, int n)
    {
        return m+n-lcs(X,Y);
    }