1. class Solution {
  2.     /**
  3.     Start from i = n, j = m. Use a StringBuilder to store characters.
  4.     While i > 0 && j > 0:
  5.         If s1.charAt(i-1) == s2.charAt(j-1)
  6.             → This character is part of both strings
  7.             → append it and move diagonally (i--, j--)
  8.  
  9.         Else if t[i-1][j] > t[i][j-1]
  10.             → append s1.charAt(i-1)
  11.             → move up (i--)
  12.  
  13.         Else
  14.             → append s2.charAt(j-1)
  15.             → move left (j--)
  16.     If one string still has characters left:
  17.         append remaining s1
  18.         append remaining s2
  19.     Reverse the StringBuilder at the end (because we built it backwards).
  20.     */
  21.     public String shortestCommonSupersequence(String str1, String str2) {
  22.         int n = str1.length();
  23.         int m = str2.length();
  24.  
  25.         // create a matrix
  26.         int[][] t = new int[n+1][m+1];
  27.  
  28.         // initialise the matrix with base condition
  29.         for(int i=0; i<n+1; i++)
  30.         {
  31.             for(int j=0; j<m+1; j++)
  32.             {
  33.                 if(i == 0 || j == 0)
  34.                     t[i][j] = 0;
  35.             }
  36.         }
  37.  
  38.         // fill the matrix
  39.         for(int i=1; i<n+1; i++)
  40.         {
  41.             for(int j=1; j<m+1; j++)
  42.             {
  43.                 if(str1.charAt(i-1) == str2.charAt(j-1))
  44.                 {
  45.                     t[i][j] = 1 + t[i-1][j-1];
  46.                 }
  47.                 else
  48.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  49.             }
  50.         }
  51.  
  52.         // Backtrack to construct the SCS string
  53.         int i=n;
  54.         int j=m;
  55.         String s = "";
  56.         while(i>0 && j>0)
  57.         {
  58.             if(str1.charAt(i-1) == str2.charAt(j-1))
  59.             {
  60.                 s += str1.charAt(i-1);
  61.                 // move diagonally
  62.                 i--;
  63.                 j--;
  64.             }
  65.             else
  66.             {
  67.                 if(t[i-1][j] > t[i][j-1])
  68.                 {
  69.                     s += str1.charAt(i-1);
  70.                     // move up
  71.                     i--;
  72.                 }
  73.                 else
  74.                 {
  75.                     s += str2.charAt(j-1);
  76.                     // move left
  77.                     j--;
  78.                 }
  79.             }
  80.         }
  81.  
  82.         while(i>0)
  83.         {
  84.             s += str1.charAt(i-1);
  85.             i--;
  86.         }
  87.  
  88.         while(j>0)
  89.         {
  90.             s += str2.charAt(j-1);
  91.             j--;
  92.         }
  93.         return new StringBuilder(s).reverse().toString();
  94.     }
  95. }