# Printing Shortest Common Supersequence

Given two strings X and Y, print the shortest string that has both X and Y as subsequences. If multiple shortest supersequence exists, print any one of them.

Examples:

Input: X = "AGGTAB",  Y = "GXTXAYB"
Output: "AGXGTXAYB" OR "AGGXTXAYB"
OR Any string that represents shortest
supersequence of X and Y

Input: X = "HELLO",  Y = "GEEK"
Output: "GEHEKLLO" OR "GHEEKLLO"
OR Any string that represents shortest
supersequence of X and Y

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have discussed how to print length of shortest possible supersequence for two given strings here. In this post, we print the shortest supersequence.

We have already discussed below algorithm to find length of shortest supersequence in previous post-

Let X[0..m-1] and Y[0..n-1] be two strings and m and be respective
lengths.

if (m == 0) return n;
if (n == 0) return m;

// If last characters are same, then add 1 to result and
// recur for X[]
if (X[m-1] == Y[n-1])
return 1 + SCS(X, Y, m-1, n-1);

// Else find shortest of following two
//  a) Remove last character from X and recur
//  b) Remove last character from Y and recur
else return 1 + min( SCS(X, Y, m-1, n), SCS(X, Y, m, n-1) );

The following table shows steps followed by the above algorithm if we solve it in bottom-up manner using Dynamic Programming for strings X = “AGGTAB” and Y = “GXTXAYB”,

Using the DP solution matrix, we can easily print shortest supersequence of two strings by following below steps –

We start from the bottom-right most cell of the matrix and
push characters in output string based on below rules-

1. If the characters corresponding to current cell (i, j)
in X and Y are same, then the character is part of shortest
supersequence. We append it in output string and move
diagonally to next cell (i.e. (i - 1, j - 1)).

2. If the characters corresponding to current cell (i, j)
in X and Y are different, we have two choices -

If matrix[i - 1][j] > matrix[i][j - 1],
we add character corresponding to current
cell (i, j) in string Y in output string
and move to the left cell i.e. (i, j - 1)
else
we add character corresponding to current
cell (i, j) in string X in output string
and move to the top cell i.e. (i - 1, j)

3. If string Y reaches its end i.e. j = 0, we add remaining
characters of string X in the output string
else if string X reaches its end i.e. i = 0, we add
remaining characters of string Y in the output string.

Below is the implementation of above idea –

## C++

 /* A dynamic programming based C++ program print    shortest supersequence of two strings */ #include using namespace std;    // returns shortest supersequence of X and Y string printShortestSuperSeq(string X, string Y) {     int m = X.length();     int n = Y.length();        // dp[i][j] contains length of shortest supersequence     // for X[0..i-1] and Y[0..j-1]     int dp[m + 1][n + 1];        // Fill table in bottom up manner     for (int i = 0; i <= m; i++)     {         for (int j = 0; j <= n; j++)         {             // Below steps follow recurrence relation             if(i == 0)                 dp[i][j] = j;             else if(j == 0)                 dp[i][j] = i;             else if(X[i - 1] == Y[j - 1])                 dp[i][j] = 1 + dp[i - 1][j - 1];             else                 dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);         }     }        // Following code is used to print shortest supersequence        // dp[m][n] stores the length of the shortest supersequence     // of X and Y     int index = dp[m][n];        // string to store the shortest supersequence     string str;        // Start from the bottom right corner and one by one     // push characters in output string     int i = m, j = n;     while (i > 0 && j > 0)     {         // If current character in X and Y are same, then         // current character is part of shortest supersequence         if (X[i - 1] == Y[j - 1])         {             // Put current character in result             str.push_back(X[i - 1]);                // reduce values of i, j and index             i--, j--, index--;         }            // If current character in X and Y are different         else if (dp[i - 1][j] > dp[i][j - 1])         {             // Put current character of Y in result             str.push_back(Y[j - 1]);                // reduce values of j and index             j--, index--;         }         else         {             // Put current character of X in result             str.push_back(X[i - 1]);                // reduce values of i and index             i--, index--;         }     }        // If Y reaches its end, put remaining characters     // of X in the result string     while (i > 0)     {         str.push_back(X[i - 1]);         i--, index--;     }        // If X reaches its end, put remaining characters     // of Y in the result string     while (j > 0)     {         str.push_back(Y[j - 1]);         j--, index--;     }        // reverse the string and return it     reverse(str.begin(), str.end());     return str; }    // Driver program to test above function int main() {     string X = "AGGTAB";     string Y = "GXTXAYB";        cstr << printShortestSuperSeq(X, Y);        return 0; }

## Java

 /* A dynamic programming based Java program print  shortest supersequence of two strings */ class GFG {        // returns shortest supersequence of X and Y      static String printShortestSuperSeq(String X, String Y)     {         int m = X.length();         int n = Y.length();            // dp[i][j] contains length of          // shortest supersequence          // for X[0..i-1] and Y[0..j-1]          int dp[][] = new int[m + 1][n + 1];            // Fill table in bottom up manner          for (int i = 0; i <= m; i++)          {             for (int j = 0; j <= n; j++)              {                                    // Below steps follow recurrence relation                  if (i == 0)                  {                     dp[i][j] = j;                 }                  else if (j == 0)                  {                     dp[i][j] = i;                 }                  else if (X.charAt(i - 1) == Y.charAt(j - 1))                  {                     dp[i][j] = 1 + dp[i - 1][j - 1];                 }                 else                  {                     dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);                 }             }         }            // Following code is used to print          // shortest supersequence dp[m][n] s         // tores the length of the shortest         // supersequence of X and Y          int index = dp[m][n];            // string to store the shortest supersequence          String str = "";            // Start from the bottom right corner and one by one          // push characters in output string          int i = m, j = n;         while (i > 0 && j > 0)                    {             // If current character in X and Y are same, then              // current character is part of shortest supersequence              if (X.charAt(i - 1) == Y.charAt(j - 1))                             {                 // Put current character in result                  str += (X.charAt(i - 1));                    // reduce values of i, j and index                  i--;                 j--;                 index--;             }                             // If current character in X and Y are different              else if (dp[i - 1][j] > dp[i][j - 1])             {                                    // Put current character of Y in result                  str += (Y.charAt(j - 1));                    // reduce values of j and index                  j--;                 index--;             }              else              {                                    // Put current character of X in result                  str += (X.charAt(i - 1));                    // reduce values of i and index                  i--;                 index--;             }         }            // If Y reaches its end, put remaining characters          // of X in the result string          while (i > 0)          {             str += (X.charAt(i - 1));             i--;             index--;         }            // If X reaches its end, put remaining characters          // of Y in the result string          while (j > 0)         {             str += (Y.charAt(j - 1));             j--;             index--;         }            // reverse the string and return it          str = reverse(str);         return str;     }        static String reverse(String input)      {         char[] temparray = input.toCharArray();         int left, right = 0;         right = temparray.length - 1;            for (left = 0; left < right; left++, right--)         {             // Swap values of left and right              char temp = temparray[left];             temparray[left] = temparray[right];             temparray[right] = temp;         }         return String.valueOf(temparray);     }            // Driver code     public static void main(String[] args)      {         String X = "AGGTAB";         String Y = "GXTXAYB";         System.out.println(printShortestSuperSeq(X, Y));     } }     // This code is contributed by 29AjayKumar

## C#

 /* A dynamic programming based C# program print  shortest supersequence of two strings */ using System;    class GFG {        // returns shortest supersequence of X and Y      static String printShortestSuperSeq(String X, String Y)     {         int m = X.Length;         int n = Y.Length;            // dp[i,j] contains length of          // shortest supersequence          // for X[0..i-1] and Y[0..j-1]          int [,]dp = new int[m + 1, n + 1];         int i, j;                    // Fill table in bottom up manner          for (i = 0; i <= m; i++)          {             for (j = 0; j <= n; j++)              {                                    // Below steps follow recurrence relation                  if (i == 0)                  {                     dp[i, j] = j;                 }                  else if (j == 0)                  {                     dp[i, j] = i;                 }                  else if (X[i - 1] == Y[j - 1])                  {                     dp[i, j] = 1 + dp[i - 1, j - 1];                 }                 else                 {                     dp[i, j] = 1 + Math.Min(dp[i - 1, j], dp[i, j - 1]);                 }             }         }            // Following code is used to print          // shortest supersequence dp[m,n] s         // tores the length of the shortest         // supersequence of X and Y          int index = dp[m, n];            // string to store the shortest supersequence          String str = "";            // Start from the bottom right corner and one by one          // push characters in output string          i = m; j = n;         while (i > 0 && j > 0)                    {             // If current character in X and Y are same, then              // current character is part of shortest supersequence              if (X[i - 1] == Y[j - 1])                             {                 // Put current character in result                  str += (X[i - 1]);                    // reduce values of i, j and index                  i--;                 j--;                 index--;             }                             // If current character in X and Y are different              else if (dp[i - 1, j] > dp[i, j - 1])             {                                    // Put current character of Y in result                  str += (Y[j - 1]);                    // reduce values of j and index                  j--;                 index--;             }              else             {                                    // Put current character of X in result                  str += (X[i - 1]);                    // reduce values of i and index                  i--;                 index--;             }         }            // If Y reaches its end, put remaining characters          // of X in the result string          while (i > 0)          {             str += (X[i - 1]);             i--;             index--;         }            // If X reaches its end, put remaining characters          // of Y in the result string          while (j > 0)         {             str += (Y[j - 1]);             j--;             index--;         }            // reverse the string and return it          str = reverse(str);         return str;     }        static String reverse(String input)      {         char[] temparray = input.ToCharArray();         int left, right = 0;         right = temparray.Length - 1;            for (left = 0; left < right; left++, right--)         {             // Swap values of left and right              char temp = temparray[left];             temparray[left] = temparray[right];             temparray[right] = temp;         }         return String.Join("",temparray);     }            // Driver code     public static void Main(String[] args)      {         String X = "AGGTAB";         String Y = "GXTXAYB";         Console.WriteLine(printShortestSuperSeq(X, Y));     } }    /* This code has been contributed  by PrinciRaj1992*/

Output:

AGXGTXAYB

Time complexity of above solution is O(n2).
Auxiliary space used by the program is O(n2).