Print Shortest Common Supersequence

'''
LCS Variation — Shortest Common Supersequence (SCS)

WHAT IS SCS?
------------
A string that contains both s1 and s2 as subsequences.

    s1 = "abac"
    s2 = "cab"
    SCS = "cabac"  → you can extract both s1 and s2 from this as subsequences.

WHY USE LCS?
------------
SCS length = len(s1) + len(s2) - LCS length

The idea: characters that are common to both strings (i.e., part of LCS)
don't need to be written twice — once serves both strings.
Every non-LCS character is unique to one string, so it must appear separately.

    s1="abac", s2="cab", LCS="ab" (length 2)
    SCS length = 4 + 3 - 2 = 5  →  "cabac" ✓

STEP 1 — BUILD THE DP TABLE:
-----------------------------
dp[i][j] = LCS length between s1[0..i] and s2[0..j]

Run the standard LCS memoization. After this, the dp table is fully filled
and ready to be traced back.

STEP 2 — TRACEBACK TO BUILD THE SCS STRING:
--------------------------------------------
Start from i = len(s1)-1, j = len(s2)-1 and walk backwards.
At each step, ask: "which character belongs here in the SCS?"

There are two cases:

CASE 1 — Characters match (s1[i] == s2[j]):
    This character is part of the LCS.
    LCS characters are written ONCE — they satisfy both strings simultaneously.
    → Add s1[i] (or s2[j], same thing) to answer, move diagonally: i--, j--

CASE 2 — Characters don't match:
    Figure out which character was "ignored" (skipped) to build the LCS.

        up   = dp[i-1][j]   # LCS value if we ignore s1[i]
        left = dp[i][j-1]   # LCS value if we ignore s2[j]

    The LCS came from the LARGER of these two directions.

    if up > left:
        → LCS was built by ignoring s1[i]
        → So s1[i] is NOT in the LCS — it's unique to s1
        → We must include it in SCS now, then move i--

    else (left >= up):
        → LCS was built by ignoring s2[j]
        → So s2[j] is NOT in the LCS — it's unique to s2
        → We must include it in SCS now, then move j--

    KEY INSIGHT: In LCS traceback, we moved toward the LARGER side to find
    common characters. Here we do the SAME — but instead of printing the
    common character, we print the character that got IGNORED (the one
    belonging to the string we're moving away from). That ignored character
    is non-LCS, so it must appear in SCS on its own.

STEP 3 — DRAIN REMAINING CHARACTERS:
--------------------------------------
When one pointer goes out of bounds, the other string still has characters left.
ALL of them must be included — skipping any character would break the
subsequence property for that string.

    while i >= 0: add s1[i], i--
    while j >= 0: add s2[j], j--

STEP 4 — REVERSE:
-----------------
Since we built the answer backwards (from end to start), reverse it at the end.

IN ONE LINE:
------------
LCS characters are written ONCE (shared by both strings).
Non-LCS characters are written SEPARATELY (each string owns its own).
The traceback simply figures out, at each step, which string "owns"
the current character — and the dp values tell you exactly that.
'''

def fun(s1,s2,n,m,dp):
    if n<0 or m<0:
        return 0
    if dp[n][m]!=-1:
        return dp[n][m]
    if s1[n]==s2[m]:
        dp[n][m]=1+fun(s1,s2,n-1,m-1,dp)
    else:
        dp[n][m]=max(fun(s1,s2,n-1,m,dp) , fun(s1,s2,n,m-1,dp))
    return dp[n][m]

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        dp=[[-1]*len(str2) for _ in range(len(str1))]
        fun(str1,str2,len(str1)-1,len(str2)-1,dp)

        i=len(str1)-1
        j=len(str2)-1
        ans=''
        while i>=0 and j>=0:
            if str1[i]==str2[j]:
                ans+=str1[i]
                i-=1
                j-=1
            else:
                up=dp[i-1][j] if i-1>=0 else 0 #here up is ignoring the ith character
                left=dp[i][j-1] if j-1>=0 else 0 #here left is ignoring the jth character

                if up>left: #it means,subsequence is coming from the top means LCS ignored the ith char so include str1[i] in scs seprately
                    ans+=str1[i]
                    i-=1
                else:
                    ans+=str2[j]
                    j-=1

        while i>=0:
            ans+=str1[i]
            i-=1
        while j>=0:
            ans+=str2[j]
            j-=1

        return ''.join(reversed(ans))