class Solution {
    /**
    Start from i = n, j = m. Use a StringBuilder to store characters.
    While i > 0 && j > 0:
        If s1.charAt(i-1) == s2.charAt(j-1)
            → This character is part of both strings
            → append it and move diagonally (i--, j--)

        Else if t[i-1][j] > t[i][j-1]
            → append s1.charAt(i-1)
            → move up (i--)

        Else
            → append s2.charAt(j-1)
            → move left (j--)
    If one string still has characters left:
        append remaining s1
        append remaining s2
    Reverse the StringBuilder at the end (because we built it backwards).
    */
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();

        // create a matrix
        int[][] t = new int[n+1][m+1];

        // initialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<m+1; j++)
            {
                if(i == 0 || j == 0)
                    t[i][j] = 0;
            }
        }

        // fill the matrix
        for(int i=1; i<n+1; i++)
        {
            for(int j=1; j<m+1; j++)
            {
                if(str1.charAt(i-1) == str2.charAt(j-1))
                {
                    t[i][j] = 1 + t[i-1][j-1];
                }
                else
                    t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
            }
        }

        // Backtrack to construct the SCS string
        int i=n;
        int j=m;
        String s = "";
        while(i>0 && j>0)
        {
            if(str1.charAt(i-1) == str2.charAt(j-1))
            {
                s += str1.charAt(i-1);
                // move diagonally
                i--;
                j--;
            }
            else
            {
                if(t[i-1][j] > t[i][j-1])
                {
                    s += str1.charAt(i-1);
                    // move up
                    i--;
                }
                else
                {
                    s += str2.charAt(j-1);
                    // move left
                    j--;
                }
            }
        }

        while(i>0)
        {
            s += str1.charAt(i-1);
            i--;
        }

        while(j>0)
        {
            s += str2.charAt(j-1);
            j--;
        }
        return new StringBuilder(s).reverse().toString();
    }
}