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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

		
s = input()
t = input()
 
dp = [[0]*(len(t)+1) for _ 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] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            
y = len(s)
x = len(t)
ans = ""
while 1:
	
	if x*y == 0:
		break
	elif s[y-1] == t[x-1]:
		ans += s[y-1]
		x -= 1
		y -= 1
	else:
		if dp[y][x] == dp[y-1][x]:
			y -= 1
		elif dp[y][x] == dp[y][x-1]:
			x -= 1
            
print(ans[::-1])

Solution (Python):
s1=input()
s2=input()
n=len(s1)
m=len(s2)

dp=[[0 for i in range(m+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+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])

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=s1[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 i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dpp = dp[i][j] + 1
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dpp)
        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])

u = ''
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:
        u = s[i - 1] + u
        i -= 1
        j -= 1

print(u)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = input()
t = input()

S,T = len(s),len(t)
dp = [[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(S):
  for j in range(T):
    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])

ans=''
while(S>=0 and T>=0):
  if dp[S][T] == dp[S-1][T]:
    S-=1
  elif dp[S][T] == dp[S][T-1]:
    T-=1
  else:
    ans = s[S-1] + ans
    S -=1
    T -=1
print(ans)

Solution (Python):
s = input()
t = input()
a = len(list(s))
b = len(list(t))

INF = float('inf')
dp = [[-INF for j in range(b+1)] for i in range(a+1)]
for i in range(a+1):
    dp[i][0] = 0
for j in range(b+1):
    dp[0][j] = 0
for i, x in enumerate(list(s)):
    for j, y in enumerate(list(t)):
        if x == y:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

ans = ''
while a > 0 and b >0:

    if dp[a][b] == dp[a-1][b]:
        a -= 1
    elif dp[a][b] == dp[a][b-1]:
        b -= 1
    else:
        ans = list(s)[a-1] + ans
        a -= 1
        b -= 1
print(ans)

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from  collections import defaultdict





def solve(test):
	s = [''] + list(input())
	t = [''] + list(input())
	rec = [[0 for j in range(len(t))] for i in range(len(s))]
	for i in range(1, len(s)):
		for j in range(1, len(t)):
			if s[i] == t[j]:
				rec[i][j] = 1 + rec[i - 1][j - 1]
			else:
				rec[i][j] = max(rec[i - 1][j], rec[i][j - 1])

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

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


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)

Solution (Python):
import sys
readline = sys.stdin.readline

s = readline().rstrip()
t = readline().rstrip()
 
def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    
    S = ''
    i,j = i+1,j+1
    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,j = i-1,j-1
            S += X[i]
    S = S[::-1]
    return S
 
print(LCS(s,t))

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

  ns=len(s)
  nt=len(t)

  dp=[[0]*(ns+1) for _ in range(nt+1)]

  for i in range(nt):
    for j in range(ns):
      if t[i]==s[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])

  ans=[]
  i=nt
  j=ns
  while dp[i][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]:
      i-=1
      j-=1
    elif dp[i][j]==dp[i-1][j-1]+1:
      i-=1
      j-=1
      ans.append(t[i])

  ans.reverse()
  return ''.join(ans)


print(main())

Solution (Python):
X = input()
Y = input()
dp = [[0 for j in range(len(Y)+1)] for i in range(len(X)+1)]
fxy = [[(0, 0) for j in range(len(Y)+1)] for i in range(len(X)+1)]
for i in range(len(X)):
    for j in range(len(Y)):
        if X[i] == Y[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            fxy[i+1][j+1] = (i, j)
        elif dp[i+1][j] >= dp[i][j+1]:
            dp[i+1][j+1] = dp[i+1][j]
            fxy[i+1][j+1] = (i+1, j)
        else:
            dp[i+1][j+1] = dp[i][j+1]
            fxy[i+1][j+1] = (i, j+1)
ans = ''
px, py = -1, -1
while not(px == py == 0):
    cx, cy = fxy[px][py]
    if dp[px][py] != dp[cx][cy]:
        ans += X[cx]
    px, py = cx, cy
print(ans[::-1])

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[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
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]

    ans = []
    i, j = N, M
    while i and j:
        if S[i - 1] == T[j - 1]:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            i -= 1

    print(''.join(reversed(ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    prev = [[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
                prev[i + 1][j + 1] = (i, j)
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                prev[i + 1][j + 1] = (i + 1, j)
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]
                prev[i + 1][j + 1] = (i, j + 1)

    ans = []
    i, j = N, M
    while i and j:
        p, q = prev[i][j]
        if i > p and j > q:
            ans.append(S[p])
        i, j = p, q

    print(''.join(reversed(ans)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
s=input()
t=input()
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i,sele in enumerate(s):
  for j ,tele in enumerate(t):
    if sele==tele:
      dp[i+1][j+1]=dp[i][j] +1
    else :
      dp[i+1][j+1]=dp[i+1][j] if dp[i+1][j]>=dp[i][j+1] else dp[i][j+1]     
res=""
i=len(s)
j=len(t)

while True:

  
  if i-1>=0:
    if dp[i-1][j]==dp[i][j]:
      i=i-1
      continue
  if j-1>=0:
    if dp[i][j-1]==dp[i][j]:
      j=j-1
      continue
  if i-1>=0 and j-1>=0:
    if dp[i-1][j-1]==dp[i][j]-1:
      j=j-1
      i=i-1
      res=s[i]+res
      
      if dp[i][j]==0:
        break
      continue
  break
print(res)

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif 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])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = inp().strip(); s2 = inp().strip()
	print(LCS(s1, s2))


if __name__ == "__main__":
	solve()

Solution (Python):
import sys
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

def LCS(s, t):
	n, m = len(s), len(t)
	dp = [[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n+1):
		for j in range(m+1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif 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])
	index = dp[n][m]
	ans = [" "]*index
	i, j = n, m
	while index:
		if s[i-1] == t[j-1]:
			ans[index-1] =  s[i-1]
			index -= 1
			i -= 1; j -= 1
		elif dp[i-1][j] > dp[i][j-1]:
			i -= 1
		else:
			j -= 1
	return(("").join(ans))

def solve():
	s1 = inp().strip(); s2 = inp().strip()
	print(LCS(s1, s2))


if __name__ == "__main__":
	solve()

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








s=s0()
t=s0()

len_s=len(s)
len_t=len(t)

dp=[[0]*(len_t+1) for _ 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],dp[i][j+1],dp[i][j]+1)
        else:
            dp[i+1][j+1]=max(dp[i+1][j],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] 
        i -= 1
        j -= 1
print(ans[::-1])

Solution (Python):
n=input()
m=input()
x=len(n)
 
y=len(m)
 
dp=[[0 for i in range(y+1)] for j in range(x+1)]

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

Solution (Python):
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]

for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
j=y
i=x
ans=""

while i>0 and j>0:
    if(n[i-1]==m[j-1]):
        
        ans=ans+n[i-1]
        
        i=i-1
        j=j-1
    else:
        mx=max(dp[i-1][j],dp[i][j-1])
        if mx==dp[i-1][j]:
            i=i-1
        else:
            j=j-1
print(ans[::-1])

Solution (Python):
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]

for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
j=y
i=x
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:
    ans = n[i-1]+ans
    i -= 1
    j -= 1
print(ans)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j] - length of the longest common subsequence
    OPT[i][j] = max(OPT[i-1][j-1]+(1 if s[i] == t[j] else 0),
                    OPT[i-1][j],
                    OPT[i][j-1])
    """
    s = input().strip()
    t = input().strip()
    OPT = [[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):
            OPT[i][j] = max(OPT[i-1][j-1]+(1 if s[i-1] == t[j-1] else 0),
                            OPT[i-1][j],
                            OPT[i][j-1])
    i, j = len(s), len(t)
    ans = []
    while i != 0 and j != 0:
        if OPT[i][j] == OPT[i-1][j]:
            i -= 1
        elif OPT[i][j] == OPT[i][j-1]:
            j -= 1
        else:
            ans.append(s[i-1])
            i -= 1
            j -= 1
    return ''.join(ans[::-1])


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

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

if __name__ == "__main__":
    main()

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

Solution (Python):

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

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

Ns = len(S)
Nt = len(T)

dp = [[0]*(Nt+1) for _ in range(Ns+1)]
path = [[None for _ in range(Nt+1)] for _ in range(Ns+1)]

for i in range(Ns):
    for j in range(Nt):
        if S[i]==T[j]:
            if dp[i+1][j+1] < dp[i][j]+1:
                dp[i+1][j+1] = dp[i][j]+1
                path[i+1][j+1] = (i,j)
        else:
            if dp[i][j+1] < dp[i+1][j]:
                dp[i+1][j+1] = dp[i+1][j]
                path[i+1][j+1] = (i+1,j)
            else:
                dp[i+1][j+1] = dp[i][j+1]
                path[i+1][j+1] = (i,j+1)


ans = []
cur = [Ns, Nt]
while cur[0] != 0 and cur[1] != 0:
    nxt = path[cur[0]][cur[1]]
    if cur[0]-1 == nxt[0] and cur[1]-1==nxt[1]:
        ans.append(S[cur[0]-1])
    cur[0] = nxt[0]
    cur[1] = nxt[1]
answer = ''.join(reversed(ans))
print(answer)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[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):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res.append(S[i - 1])
            i -= 1
            j -= 1

    print("".join(res[::-1]))


if __name__ == '__main__':
    resolve()

Solution (Python):
def main():
    s = input()
    t = input()
    lens = len(s)
    lent = len(t)
    
    dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(lens):
        for j in range(lent):
            if s[i]==t[j]:
                dp[i+1][j+1] = max(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,j = lens,lent
    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)

main()

Solution (Python):
import sys
input = sys.stdin.readline

s = input().rstrip()
t = input().rstrip()
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 > 0 and lt > 0:
  if dp[ls][lt] == dp[ls-1][lt]:
    ls -= 1
  elif dp[ls][lt] == dp[ls][lt-1]:
    lt -= 1
  else:
    ans = s[ls-1] + ans
    ls -= 1
    lt -= 1
print(ans)

Solution (Python):
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for i in range(m+1)] for j 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][j+1],dp[i+1][j])
ans=''
a=n
b=m
while a>0 and b>0:
  if dp[a][b]==dp[a-1][b]:
    a-=1
  elif dp[a][b]==dp[a][b-1]:
    b-=1
  else:
    a-=1
    b-=1
    ans=s[a]+ans
print(ans)

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

for i in range(len(t)):
    for j in range(len(s)):
        if t[i] == s[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])
cnt = dp[m][n]
ans = ''
while n > 0 and m > 0:
    if dp[m][n] == dp[m][n - 1]:
        n -= 1
    elif dp[m][n] == dp[m - 1][n]:
        m -= 1
    else:
        ans = s[n - 1] + ans
        n -= 1
        m -= 1

print(ans)

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

dp = [[0] * (len(t) + 1) for _ 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:
        i -= 1
        j -= 1
        ans = s[i] + ans

print(ans)

Solution (Python):
import numpy as np

S = np.array([ord(i) - 97 for i in input()], dtype=int)
T = np.array([ord(i) - 97 for i in input()], dtype=int)
ls = len(S)
lt = len(T)

equal = np.equal.outer(S,T).astype(int)

 
dp = [np.zeros(lt + 1,dtype = int)]

for i in range(ls):
  
  x = dp[-1].copy()
  newDP = x.copy()
  
  newDP[1:] = np.maximum(x[:-1] + equal[i],newDP[1:])
  
  np.maximum.accumulate(newDP, out = newDP)
  
  
  dp.append(newDP)
  
 
 
ans = ""
i, j = ls, lt

while i > 0 and j > 0:
  if S[i - 1] == T[j - 1]:
    ans += chr(S[i - 1] + 97)
    i -= 1
    j -= 1
    continue
  if dp[i][j] == dp[i - 1][j]:
    i -= 1
  else:
    j -= 1


print(ans[::-1])

Solution (Python):
import sys
input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]
dp = [[0]*(len(t)+1) for _ 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] = dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]

ci, cj = len(s), len(t)
ans = []

while ci!=0 and cj!=0:
    if s[ci-1]==t[cj-1]:
        ci -= 1
        cj -= 1
        ans.append(s[ci])
    else:
        if dp[ci][cj]==dp[ci-1][cj]:
            ci -= 1
        else:
            cj -= 1

ans.reverse()
print(''.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
track = [[-1]*(len(t)+1) for _ 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] = dp[i][j]+1
            track[i+1][j+1] = (i, j)
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]
                track[i+1][j+1] = (i+1, j)
            else:
                dp[i+1][j+1] = dp[i][j+1]
                track[i+1][j+1] = (i, j+1)

ci, cj = len(s), len(t)
ans = []

while ci!=0 and cj!=0:
    ni, nj = track[ci][cj]
    
    if ci-ni==1 and cj-nj==1:
        ans.append(s[ni])
    
    ci, cj = ni, nj

ans.reverse()
print(''.join(ans))

Solution (Python):
def solve():
    s = input()
    t = input()
    s_size = len(s)
    t_size = len(t)
    dp = [[0 for i in range(s_size+1)] for j in range(t_size+1)]
    for i in range(1, t_size+1):
        for j in range(1, s_size+1):
            if t[i-1] == s[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    ans = ""
    i, j = t_size, s_size
    while i > 0 and j > 0:
        if dp[i][j] == dp[i][j-1]:
            j -= 1
        elif dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            ans = t[i-1] + ans
            i -= 1
            j -= 1
    print(ans)
solve()

Solution (Python):
s=input()
t=input()
S=len(s)
T=len(t)
ans=[[0 for e in range(S+1)] for f in range(T+1)]
chk=[]
for a in range(1,T+1):
 for b in range(1,S+1):
  if t[a-1]==s[b-1]:
   ans[a][b]=ans[a-1][b-1]+1
  else:
   if ans[a-1][b]>ans[a][b-1]:
    ans[a][b]=ans[a-1][b]
   else:
    ans[a][b]=ans[a][b-1]
x,y=T,S
while x>0 and y>0:
 if ans[x][y]==ans[x-1][y]:
  x-=1
 elif ans[x][y]==ans[x][y-1]:
  y-=1
 else:
  x-=1
  y-=1
  chk.append(s[y])
chk.reverse()
print("".join(chk))

Solution (Python):
def lcs(s1,s2,m,n,t):
    l=[]
    for i in range(0,m+1):
        t[i][0]=0
    for i in range(1,n+1):
        t[0][i]=0
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]:
                t[i][j]=t[i-1][j-1]+1
            else:
                t[i][j]=max(t[i-1][j],t[i][j-1])
    i=m
    j=n
    while(i>0 and j>0):
        if s1[i-1]==s2[j-1]:
            l.append(s1[i-1])
            i-=1
            j-=1
        else:
            if t[i-1][j]>t[i][j-1]:
                i-=1
            else:
                j-=1
    l.reverse()  
    if len(l)==0:b=""
    else:b="".join(str(a) for a in l)
    return b
s1=input()
s2=input()
m=len(s1)
n=len(s2)
t=[[0 for x in range(n+1)] for x in range(m+1)] 
d=lcs(s1,s2,m,n,t)
print(d)

Solution (Python):
s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for j in range(T+1)] for i in range(S+1)]
for i in range(S):
    for j in range(T):
        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])
a = ""
i += 1
j += 1
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
        a = s[i] + a

print(a)

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

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    
    S = ''
    i,j = i+1,j+1
    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,j = i-1,j-1
            S += X[i]
    S = S[::-1]
    return S

print(LCS(s,t))

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

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    
    idx = dp[XL][YL]-1
    S = [0]*(idx+1)
    i,j = i+1,j+1
    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,j = i-1,j-1
            S[idx] = X[i]
            idx -= 1
    return S

print(''.join(LCS(s,t)))

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

def LCS(X,Y):
    XL = len(X)
    YL = len(Y)
    dp = [[0 for j in range(YL+1)] for i in range(XL+1)]
    for i in range(XL):
        for j in range(YL):
            if X[i] == Y[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])
    
    idx = dp[XL][YL]-1
    S = [0 for i in range(idx+1)]
    i,j = XL,YL
    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
            S[idx] = X[i]
            idx -= 1
    return S

print(''.join(LCS(s,t)))

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

S = list(ST())
T = list(ST())
dp = FILL2(0,len(S)+1,len(T)+1)
for i in range(len(S)+1):
    for j in range(len(T)+1):
        if i+1<=len(S) and j+1<=len(T):
            if S[i]==T[j]:
                dp[i+1][j+1] = dp[i][j] + 1
        if i+1<=len(S):
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        if j+1 <= len(T):
            dp[i][j+1] = max(dp[i][j+1],dp[i][j])

l = dp[len(S)][len(T)]
i = len(S)
j = len(T)
ans = ''
while l > 0:
    if S[i-1]==T[j-1]:
        i -= 1
        j -= 1
        l -= 1
        ans = S[i]+ans
    else:
        if dp[i][j-1]==dp[i][j]:
            j -= 1
        else:
            i -= 1
print(ans)

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] = dp[i-1][j-1]+1
    else: dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      
i, j = len(s), len(t)
f = ""

while((i>0) & (j>0)):
  if dp[i][j] == dp[i-1][j]: i -= 1
  elif dp[i][j] == dp[i][j-1]: j -= 1
  else :
    f += s[i-1]
    i -= 1
    j -= 1
  
print(f[::-1])