Problem:
 Score : 100 points    Problem Statement You are given strings s and t .
Find one longest string that is a subsequence of both s and t .      Notes A subsequence of a string x is the string obtained by removing zero or more characters from x and concatenating the remaining characters without changing the order.      Constraints  s and t are strings consisting of lowercase English letters.  1 \leq |s|, |t| \leq 3000         Input Input is given from Standard Input in the following format:  s  t       Output Print one longest string that is a subsequence of both s and t .
If there are multiple such strings, any of them will be accepted.        Sample Input 1 axyb
abyxb      Sample Output 1 axb  The answer is axb or ayb ; either will be accepted.       Sample Input 2 aa
xayaz      Sample Output 2 aa       Sample Input 3 a
z      Sample Output 3   The answer is (an empty string).       Sample Input 4 abracadabra
avadakedavra      Sample Output 4 aaadara

Solution (Python):
s = input()
t = input()

dp = [ [0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+ 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])


str = ''
while(i > 0 and j > 0):
    if (dp[i][j] == dp[i-1][j]):
        i -= 1
    elif (dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        str = s[i-1] + str
        i -= 1
        j -= 1

print(str)

Solution (Python):
s = input()
n = len(s)

t = input()
m = len(t)

dp = tuple([0] * (m + 1) for _ in range(n + 1))

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

rest = dp[n][m]
ans = ''

i = n
j = m
while rest > 0:
    if s[i - 1] == t[j - 1]:
        ans = s[i - 1] + ans
        rest -= 1
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)

Solution (Python):
S = input()
T = input()

moves = [[None for i in range(len(T)+1)] for j in range(len(S)+1)]
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]



for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        sc = S[i-1]
        tc = T[j-1]

        c = 0

        if dp[i-1][j] > dp[i][j]:
            dp[i][j] = dp[i-1][j]
            c = 1
        if dp[i][j-1] > dp[i][j]:
            dp[i][j] = dp[i][j-1]
            c = 2
        if sc == tc and 1 + dp[i-1][j-1] > dp[i][j]:
            dp[i][j] = 1 + dp[i-1][j-1]
            c = 3
        moves[i][j] = c

s = ""

cur = [len(S), len(T)]
while cur != [0, 0]:
    
    move = moves[cur[0]][cur[1]]
    if move == 3:
        s += S[cur[0]-1]
        cur[0] -= 1
        cur[1] -= 1
    elif move == 2:
        cur[1] -= 1
    elif move == 1:
        cur[0] -= 1
    else:
        break


print(s[::-1])

Solution (Python):
s,t=input(),input()
ls,lt=len(s),len(t)
dp=[[0 for _ in range(lt+1)] for _ in range(ls+1)]
for i in range(ls):
    for j in range(lt):
        if s[i]==t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j],dp[i+1][j+1])
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j+1])


res =''
i,j =ls,lt
while(i>0and j>0):
    
    if dp[i][j] == dp[i-1][j]:
        i -=1
    
    elif dp[i][j] == dp[i][j-1]:
        j -=1
    
    else:
        res = s[i-1]+res
        i -=1
        j -=1
print(res)

Solution (Python):
s,t =input(),input()
inf = float('inf')
dp =[[0 for _ in range(3100)] for _ in range(3100)]

for i in range(len(s)):
    for j in range(len(t)):
        if (s[i] == t[j]):
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i + 1][j + 1] = max(dp[i+1][j+1],dp[i][j+1])

res = ''
i,j = len(s),len(t)
while (i > 0 and j >0):
    
    if (dp[i][j] == dp[i - 1][j]):
        i -= 1  
    
    elif (dp[i][j] == dp[i][j - 1]):
        j -= 1  
    
    else:
        res = s[i - 1] + res  
        i -= 1
        j -= 1  
print(res)

Solution (Python):
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

ans = ''
i = n
j = m
while i >= 0 and j >= 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])

Solution (Python):
S = input()
T = input()
memo_ls = [[] for i in range(len(S)+1)]
res = ""
for i in range(len(T) + 1):
    memo_ls[0].append(0)
path = dict()
for i in range(len(S)):
    memo_ls[i+1].append(0)
    for j in range(len(T)):
        if S[i] == T[j]:
            cost = max(memo_ls[i][j] + 1, memo_ls[i][j+1], memo_ls[i+1][j])
            memo_ls[i+1].append(cost)
        else:
            memo_ls[i+1].append(max(memo_ls[i][j+1], memo_ls[i+1][j]))

x_ind = len(T)
y_ind = len(S)
while x_ind * y_ind > 0:
    if memo_ls[y_ind][x_ind] == memo_ls[y_ind-1][x_ind]:
        y_ind -= 1
    elif memo_ls[y_ind][x_ind] == memo_ls[y_ind][x_ind-1]:
        x_ind -= 1
    else:
        res += T[x_ind-1]
        x_ind -= 1
        y_ind -= 1
print(res[::-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    s = SI()
    t = SI()

    
    dp_table_2 = [[0 for _ in range(len(s))] for _ in range(len(t))]
    
    ume = 0
    for i in range(len(s)):
        if t[0] == s[i]:
            ume = 1
        dp_table_2[0][i] = ume
    ume = 0
    for i in range(len(t)):
        if t[i] == s[0]:
            ume = 1
        dp_table_2[i][0] = ume

    
    for i in range(1, len(t)):
        for j in range(1, len(s)):
            if t[i] == s[j]:
                dp_table_2[i][j] = max(dp_table_2[i-1][j], dp_table_2[i][j-1], dp_table_2[i-1][j-1]+1)
            else:
                dp_table_2[i][j] = max(dp_table_2[i-1][j], dp_table_2[i][j-1])

    

    

    
    i = len(t) - 1
    j = len(s) - 1
    ans = ''
    while i >= 0 and j >= 0:
        if i == 0 and j == 0:
            if dp_table_2[0][0] > 0:
                ans += s[0]
            break
        if j == 0:
            if dp_table_2[i][j] != dp_table_2[i-1][j]:
                ans += t[i]
            i -= 1
            continue
        if i == 0:
            if dp_table_2[i][j] != dp_table_2[i][j-1]:
                ans += s[j]
            j -= 1
            continue
        if dp_table_2[i][j] != dp_table_2[i][j-1] and dp_table_2[i][j] != dp_table_2[i-1][j]:
            ans += t[i]
            i -= 1
            j -= 1
        elif dp_table_2[i][j] != dp_table_2[i][j-1]: 
            i -= 1
        elif dp_table_2[i][j] != dp_table_2[i-1][j]: 
            j -= 1
        else:
            j -= 1

    print(ans[::-1])

main()

Solution (Python):
def main():

    s = input()
    t = input()
    m, n = len(s), len(t)
    dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    i, j = m, n
    ans = ""
    while i > 0 and j > 0:
        if s[i-1] == t[j-1]:
            ans += s[i-1]
            i -= 1
            j -= 1
        elif dp[i][j-1] > dp[i-1][j]:
            j -= 1
        else:
            i -= 1
    return ans[::-1]


if __name__ == '__main__':
    print(main())

Solution (Python):
from io import StringIO


UP = 0
LEFT = 1
LEFTUP = 2


def lcs(s, t):
    m = len(s)
    n = len(t)
    
    dp = [[0] * (n + 1) for i in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    buf = StringIO()
    i = m
    j = n
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            buf.write(s[i - 1])
            i -= 1
            j -= 1
    buf.seek(0)
    ans = buf.read()[::-1]
    return ans


if __name__ == "__main__":
    print(lcs(input(), input()))

Solution (Python):
from io import StringIO


UP = 0
LEFT = 1
LEFTUP = 2


def lcs(s, t):
    m = len(s)
    n = len(t)
    
    dp = [[(0, None)] * (n + 1) for i in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                continue
            elif s[i - 1] == t[j - 1]:
                dp[i][j] = (dp[i - 1][j - 1][0] + 1, LEFTUP)
            elif dp[i - 1][j][0] >= dp[i][j - 1][0]:
                dp[i][j] = (dp[i - 1][j][0], UP)
            else:
                dp[i][j] = (dp[i][j - 1][0], LEFT)
    buf = StringIO()
    i = m
    j = n
    while i > 0 and j > 0:
        if dp[i][j][1] == LEFTUP:
            buf.write(t[j - 1])
            i -= 1
            j -= 1
        elif dp[i][j][1] == UP:
            i -= 1
        else:
            j -= 1
    buf.seek(0)
    ans = buf.read()[::-1]
    return ans


if __name__ == "__main__":
    print(lcs(input(), input()))

Solution (Python):
import numpy as np
 
t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')
 
ls = len(s)
lt = len(t)
 
eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]
 

for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out = prev[1:])
    np.maximum.accumulate(prev, out = prev)
    dp.append(prev)
 

 

l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
 
print(res[::-1])

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = ""; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def inp(): return int(sys.stdin.readline())
def st(): return input()
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]


def main():
    s = st()
    t = st()
    slen = len(s)
    tlen = len(t)
    
    
    dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
    
    for i in range(1, slen + 1):
        for j in range(1, tlen + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  

    

    
    length = dp[slen][tlen]
    i = slen
    j = tlen
    ans = ""
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]: 
            i -= 1
        else:
            j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = ""; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def inp(): return int(sys.stdin.readline())
def st(): return input()
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]


def main():
    s = st()
    t = st()
    slen = len(s)
    tlen = len(t)
    
    
    dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
    
    for i in range(1, slen + 1):
        for j in range(1, tlen + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  

    

    
    length = dp[slen][tlen]
    i = slen
    j = tlen
    ans = ["" for _ in range(length)]
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans[length - 1] = s[i - 1]
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]: 
            i -= 1
        else:
            j -= 1
    print("".join(ans))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
t=input()

dp=[[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1]=max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1], dp[i][j+1])

i,j=len(s),len(t)
ans=[]
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans.append(s[i])
ans.reverse()
print("".join(ans))

Solution (Python):
s = 'S' + input()
t = 'T' + input()

dp = [[0] * len(t) for _ in range(len(s))]
for i in range(len(s)) :
    for j in range(len(t)) :
        if i == 0 or j == 0 :
            continue
            
        if s[i] == t[j] :
            dp[i][j] = dp[i-1][j-1] + 1
        else :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ret = ''
i, j = len(s)-1, len(t)-1
while i >= 1 and j >= 1 :
    if dp[i][j] == dp[i-1][j] :
        i -= 1
    elif dp[i][j] == dp[i][j-1] :
        j -= 1
    else :
        ret += s[i]
        i -= 1
        j -= 1
        
print(ret[::-1])

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)



S = input().rstrip()
T = input().rstrip()

X = len(S) + 100
dp = [ [0 for _ in range(X)] for _ in range(X) ]


for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)

        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])


ans = ""
i = len(S)
j = len(T)
while i > 0 and j > 0:
    if (dp[i][j] == dp[i-1][j]):
        i -= 1
    elif (dp[i][j] == dp[i][j-1]):
        j -= 1
    else:
        ans = S[i-1]+ans
        i -= 1
        j -= 1

print(ans)

Solution (Python):
s=input()
t=input()


dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]


for sx in range(len(s)):
    for ty in range(len(t)):
        
        if s[sx]==t[ty]:dp[sx+1][ty+1]=dp[sx][ty]+1
        
        else:dp[sx+1][ty+1]=max(dp[sx+1][ty],dp[sx][ty+1])


ans=''
i=len(s)
j=len(t)
while(i>0):
    if dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1
    else:
        ans=t[j-1]+ans
        i-=1
        j-=1
print(ans)

Solution (Python):
s=input()
t=input()
S=len(s)
T=len(t)
dp=[[0]*(T+1) for _ in range(S+1)]
for i in range(1,S+1):
    for j in range(1,T+1):
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
ans=""
x=S
y=T
l=dp[-1][-1]
while len(ans)<dp[-1][-1]:
    if dp[x][y-1]==l:
        y-=1
    elif dp[x-1][y]==l:
        x-=1
    else:
        ans+=t[y-1]
        x-=1
        y-=1
        l-=1
print(ans[::-1])

Solution (Python):
s1 = input()
s2 = input()
n = len(s2);    m = len(s1)
dp = [[0 for i in range(m+1)] for i in range(n+1)]
for i in range(n):
    for j in range(m):
        if s2[i] == s1[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])







i = n;  j = m
ind = ''
while i > 0 and j > 0:
    if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
        ind = s1[j-1]+ind;  i -= 1; j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
print(ind)

Solution (Python):

ABOVE,LEFT,UPPERLEFT=1,2,3
s = str(input())
t = str(input())
ls = len(s)
lt = len(t)
dp = [[0 for j in range(lt+2)] for i in range(ls+2)]
memo = [[0 for j in range(lt+2)] for i in range(ls+2)] 
for i in range(ls+1):
    for j in range(lt+1):
        if i<ls and j<lt and s[i] == t[j]: 
            dp[i+1][j+1] = dp[i][j] + 1
            memo[i+1][j+1] = UPPERLEFT
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
            memo[i+1][j] = ABOVE
        if dp[i][j+1] < dp[i][j]:
            dp[i][j+1] = dp[i][j]
            memo[i][j+1] = LEFT

result=""
row,column=ls,lt
while(memo[row][column]!=0):
    if memo[row][column] == ABOVE:
        row -= 1
    elif memo[row][column] == LEFT:
        column -= 1
    elif memo[row][column] == UPPERLEFT:
        result = s[row-1]+result
        row -= 1
        column -= 1
print(result)

Solution (Python):
def p_f():
    S = input()
    T = input()
    s_n = len(S)
    t_n = len(T)
    dp = [[0] * (s_n + 1) for _ in range(t_n + 1)]

    for i in range(1, t_n + 1):
        f = False
        for j in range(1, s_n + 1):
            if S[j - 1] == T[i - 1]:
                f = True
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j])
                continue

            if f:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    ans = ""
    while s_n > 0 and t_n > 0:
        if dp[t_n - 1][s_n] == dp[t_n][s_n]:
            t_n -= 1

        if dp[t_n][s_n - 1] == dp[t_n][s_n]:
            s_n -= 1

        if dp[t_n - 1][s_n] != dp[t_n][s_n] and dp[t_n][s_n - 1] != dp[t_n][s_n]:
            ans = S[s_n - 1] + ans
            s_n -= 1
            t_n -= 1

    print(ans)


if __name__ == '__main__':
    p_f()

Solution (Python):
s, t = 'd'+input(), 'd'+input()
n, m = len(s)-1, len(t)-1



memo = [[0]*(m+1) for i in range(n+1)]
memo[0][0] = 0

for i in range(n):
    for j in range(m):
        if s[i+1] == t[j+1]:
            memo[i+1][j+1] = memo[i][j] + 1
        else:
            memo[i+1][j+1] = max(memo[i+1][j], memo[i][j+1])

ans = ""
i, j = n, m
while i != 0 and j != 0:
    if s[i] == t[j] and memo[i][j]-1 == memo[i-1][j-1]:
        ans += s[i]
        i -= 1
        j -= 1
    elif memo[i][j] == memo[i-1][j]:
        i -= 1
    elif memo[i][j] == memo[i][j-1]:
        j -= 1

print(ans[::-1])

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

s, t = input(), input()
ls, lt = len(s), len(t)
dp = [[0] * (lt+1) for i in range(ls+1)]
for i, x in enumerate(s, 1):
    for j, y in enumerate(t, 1):
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ans = ''
while 0 < dp[i][j]:
    if dp[i-1][j] == dp[i][j]:
        i -= 1
    elif dp[i][j-1] == dp[i][j]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans += s[i]
print(ans[::-1])

Solution (Python):
str1 = [s for s in input()]
str2 = [s for s in input()]

dp = [[0 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]

for i in range(len(str1)):
    for j in range(len(str2)):
        dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
        if str1[i] == str2[j]:
            newVal = max(dp[i + 1][j + 1] ,dp[i][j] + 1)
            dp[i + 1][j + 1] = newVal

result = ""

i = len(str1)
j = len(str2)

while i >= 0 and j >= 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    elif dp[i][j] != dp[i -1][j - 1]:
        result += str1[i -1]
        i -= 1
        j -= 1

print(result[::-1])

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    S = input().strip()
    T = input().strip()

    lenS = len(S)
    lenT = len(T)

    dp = [[0] * (lenT + 1) for _ in range(lenS + 1)]

    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = []
    now = dp[lenS][lenT]
    i = lenS
    j = lenT
    while now > 0:
        if dp[i - 1][j] == now:
            i -= 1
        elif dp[i][j - 1] == now:
            j -= 1
        else:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
            now -= 1

    print(''.join(ans[:: -1]))

sol()

Solution (Python):
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
    if s[i - 1] == t[j - 1]:
      dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + 1)
    else:
      dp[i][j] = max(dp[i][j], dp[i - 1][j], dp[i][j - 1])
u = []
while True:
  if dp[i][j] == 0:
    break
  elif dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    u.append(s[i - 1])
    i -= 1
    j -= 1
print(''.join(u[::-1]))

Solution (Python):
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
    k = dp[i - 1][j]
    if dp[i][j - 1] > k:
      k = dp[i][j - 1]
    if (s[i - 1] == t[j - 1]) and (dp[i - 1][j - 1] + 1 > k):
      k = dp[i - 1][j - 1] + 1
    dp[i][j] = k
u = []
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    u.append(s[i - 1])
    i -= 1
    j -= 1
print(''.join(reversed(u)))

Solution (Python):
s1=input()
s2=input()
dp=[0]*(len(s1)+1)
dp[0]=[0]*(len(s2)+1)
for i in range(1,len(s1)+1):
	dp[i]=[0]*(len(s2)+1)
	for j in range(1,len(s2)+1):
		if s1[i-1]==s2[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])


s=""
i,j=len(s1),len(s2)
while(i>0 and j>0):
	if s1[i-1]==s2[j-1]:
		s+=s1[i-1]
		i-=1
		j-=1
	elif dp[i][j-1]>dp[i-1][j]:
		j-=1
	else:
		i-=1
print(s[::-1])

Solution (Python):

def backtrack(C, A, B, i, j):
    out = ""
    while i != 0 and j != 0:
        if A[i - 1] == B[j - 1]:
            out = A[i - 1] + out
            i -= 1
            j -= 1
        elif C[i][j - 1] > C[i - 1][j]:
            j -= 1
        else:
            i -= 1
    return out

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])

    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("MZJAWXU", "XMJYAUZ") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"
assert lcs("a", "z") == ""

if False:
    import random
    for _ in range(1000):
        q = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        p = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        lcs("".join(q), "".join(p))

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)

Solution (Python):
s = input()
t = input()

def solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

    for i in range(L1-1, -1, -1):
        for j in range(L2-1, -1, -1):
            r = max(dp[i+1][j], dp[i][j+1])
            if S[i] == T[j]:
                r = max(r, dp[i+1][j+1] + 1)
            dp[i][j] = r

    res = []
    i = 0; j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
    return "".join(res)
print(solve(s, t))

Solution (Python):
s = tuple(input())
t = tuple(input())
n = len(s)
m = len(t)

dp = [[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

res = ''
while n != 0 and m != 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        n -= 1
        m -= 1
        res = s[n] + res
print(res)

Solution (Python):
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
    else:
      dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

Solution (Python):
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100
 
s = (raw_input())
t = (raw_input())
n=len(s)
m=len(t)
dp=[]
for i in range(n+1):
	lp=[]
	for j in range(m+1):
		lp.append(0)
	dp.append(lp)

for i in range(0,n+1):
	for j in range(0,m+1):
		if(i==0 or j==0):
			continue
		if(s[i-1]==t[j-1]):
			dp[i][j]=1+dp[i-1][j-1]
			
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
			
			
			
			
ii = dp[n][m]
ans=""
i=n
j=m
while(i>0 and j>0):
	if(s[i-1]==t[j-1]):
		ans=ans+s[i-1]
		i=i-1
		j=j-1
	elif(dp[i-1][j]>dp[i][j-1]):
		i=i-1
	else:	
		j=j-1	
print ans[::-1]

Solution (Python):
def S(): return input()


def main():
    s = [ord(c) - 97 for c in S()]
    t = [ord(c) - 97 for c in S()]
    sl = len(s)
    tl = len(t)
    rr = [[0] * (tl) for _ in range(sl)]
    t0 = t[0]
    for i in range(sl):
        if s[i] == t0:
            for k in range(i,sl):
                rr[k][0] = 1
            break

    rr0 = rr[0]
    s0 = s[0]
    for j in range(tl):
        if s0 == t[j]:
            for k in range(j,tl):
                rr0[k] = 1
            break

    ta = [(i,t[i]) for i in range(1, tl)]
    for i in range(1, sl):
        rri = rr[i]
        rri1 = rr[i-1]
        si = s[i]
        for j, tj in ta:
            if si == tj:
                rri[j] = rri1[j-1] + 1
            else:
                rri[j] = rri1[j]
                if rri[j] < rri[j-1]:
                    rri[j] = rri[j-1]

    i = sl-1
    j = tl-1
    r = []
    while i >= 0 and j >= 0:
        if s[i] == t[j]:
            r.append(s[i] + 97)
            i -= 1
            j -= 1
            continue
        if rr[i][j] == 0:
            break
        if i > 0 and rr[i-1][j] == rr[i][j]:
            i -= 1
        else:
            j -= 1

    return ''.join(map(chr,r[::-1]))


print(main())

Solution (Python):
import numpy as np

t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')

ls = len(s)
lt = len(t)

eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]


for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out = prev[1:])
    np.maximum.accumulate(prev, out = prev)
    dp.append(prev)




l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1

print(res[::-1])

Solution (Python):
s = input()
t = input()


dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]



for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])


ans = ''
i = len(s)
j = len(t)
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1
print(ans)

Solution (Python):
s=input();t=input()
ls=len(s);lt=len(t)
dp=[[0]*(lt+1) for _ in range(ls+1)]
for i in range(ls):
  for j in range(lt):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while ls and lt:
  if dp[ls][lt]==dp[ls-1][lt]:
    ls-=1
  elif dp[ls][lt]==dp[ls][lt-1]:
    lt-=1
  else:
    ls-=1;lt-=1
    ans+=s[ls]
print(ans[::-1])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
S = np.array(list(input().rstrip()), dtype='U1')
T = np.array(list(input().rstrip()), dtype='U1')

equal = (S[:,None] == T[None,:])

LS = len(S)
LT = len(T)

dp = [np.zeros(LT+1, dtype=np.int16)]

for i in range(LS):
    prev = dp[-1]
    x = prev.copy()
    np.maximum(x[1:], prev[:-1] + equal[i] * 1, out = x[1:])
    np.maximum.accumulate(x, out = x)
    dp.append(x)

x = LS
y = LT
rev_ans = []

while x >= 1 and y >= 1:
    if equal[x-1][y-1]:
        rev_ans.append(str(S[x-1]))
        x -= 1
        y -= 1
        continue
    n1 = dp[x-1][y]
    n2 = dp[x][y-1]
    if n1 < n2:
        y -= 1
        continue
    x -= 1
    continue

answer = ''.join(rev_ans[::-1])

print(answer)