def Lcs( s1: str, s2: str) -> str:
    m,n = len(s1),len(s2)
    dp = {}
    def lcs(i,j,vec):
        if (i,j) in dp:return dp[(i,j)]

        if i==m or j==n:return 0

        if s1[i]==s2[j]:
            vec.append(s1[i])
            dp[(i,j)] = 1+lcs(i+1,j+1,vec)
            return dp[(i,j)]
        else:
            dp[(i,j)] = max(lcs(i,j+1,vec),lcs(i+1,j,vec))
            return dp[(i,j)]
    vec=[]
    lcs(0,0,vec)
    print(vec)
X = "AGGTAB"
Y = "GXTXAYB"
print(Lcs(X,Y))