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



Sample input:
axyb
abyxb


Sample output:
axb

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
n = len(a)
m = len(b)

dp = []

for i in range(n+1):
    dp.append([])
    for j in range(m+1):
        dp[-1].append([0,0,0,False])

for i in range(n+1):
    dp[i][0] = [0,0,0,False]

for j in range(m+1):
    dp[0][j] = [0,0,0,False]

for i in range(1,n+1):
    for j in range(1,m+1):
        if a[i-1]==b[j-1]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = i-1
            dp[i][j][2] = j-1
            dp[i][j][3] = True
        else:
            if dp[i-1][j][0]>dp[i][j-1][0]:
                dp[i][j][0] = dp[i-1][j][0]
                dp[i][j][1] = i-1
                dp[i][j][2] = j
            else:
                dp[i][j][0] = dp[i][j-1][0]
                dp[i][j][1] = i
                dp[i][j][2] = j-1

start = [n,m]
s = ""
while start[0]>0 and start[1]>0:
    if dp[start[0]][start[1]][3]:
        s = s+a[start[0]-1]
    x = dp[start[0]][start[1]][1]
    y = dp[start[0]][start[1]][2]
    start = [x,y]
s = s[::-1]
print(s)

Submission status: Time Limit Exceeded

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

l1,l2 = len(s),len(t)

dp = [[0]*(l2+1) for _ in range(l1+1)]
memo = [['']*(l2+1) for _ in range(l1+1)]

for i in range(1,l1+1):
  for j in range(1,l2+1):
    if s[i-1]==t[j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
      memo[i][j] = s[i-1]
    else:
      if dp[i-1][j] >= dp[i][j-1]:
        dp[i][j] = dp[i-1][j]
        memo[i][j] = (i-1,j)
      else:
        dp[i][j] = dp[i][j-1]
        memo[i][j] = (i,j-1)
      
i,j = l1,l2
ans = ''
while i > 0 and j > 0:
  if len(memo[i][j]) == 2:
    i, j = memo[i][j]
  else:
    ans = memo[i][j] + ans
    i, j = i-1, j-1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

s=list(input())
t=list(input())

l1,l2 = len(s),len(t)

dp = [[[]]*(l2+1) for _ in range(l1+1)]

for i in range(1,l1+1):
  for j in range(1,l2+1):
    if s[i-1]==t[j-1]:
      dp[i][j] = deepcopy(dp[i-1][j-1])
      dp[i][j].append(s[i-1])
    else:
      if len(dp[i-1][j]) >= len(dp[i][j-1]):
        dp[i][j] = deepcopy(dp[i-1][j])
      else:
        dp[i][j] = deepcopy(dp[i][j-1])
      
print(''.join(dp[-1][-1]))

Submission status: Time Limit Exceeded

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

l1,l2 = len(s),len(t)

dp = [['']*(l2+1) for _ in range(l1+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


s=input()
t=input()
global ans
ans=""
@lru_cache(None)
def rec(i,j,x):
    global ans
    if len(x)>len(ans):
        ans=x
    if len(x)+min(abs(i-len(s)),abs(j-len(t)))<len(ans):
        return
    if i>=len(s) or j>=len(t):
        return
    if s[i]==t[j]:
        rec(i+1,j+1,x+s[i])
        return
    rec(i+1,j,x)
    rec(i,j+1,x)
rec(0,0,"")
print("".join(ans))


endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


s=input()
t=input()
global ans
ans=""
def rec(i,j,x):
    global ans
    if len(x)>len(ans):
        ans=x
    if len(x)+min(abs(i-len(s)),abs(j-len(t)))<len(ans):
        return
    if i>=len(s) or j>=len(t):
        return
    if s[i]==t[j]:
        rec(i+1,j+1,x+s[i])
        return
    rec(i+1,j,x)
    rec(i,j+1,x)
rec(0,0,"")
print("".join(ans))


endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass


s=input()
t=input()
global x,ans
x=[]
ans=[]
def rec(i,j):
    global x,ans
    if len(x)>len(ans):
        ans=x[::]
    if len(x)+min(abs(i-len(s)),abs(j-len(t)))<len(ans):
        return
    if i>=len(s) or j>=len(t):
        return
    if s[i]==t[j]:
        x.append(s[i])
        rec(i+1,j+1)
        x.pop()
        return
    rec(i+1,j)
    rec(i,j+1)
rec(0,0)
print("".join(ans))


endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Time Limit Exceeded

Solution code:
s= input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(lt+1) ]  for _ in range(ls+1)] #dp[i][j] sがi文字目,tがj文字目まででのLCS
for ids in range(1,ls+1):
    for idt in range(1,lt + 1):
        #一致してたら文字を足す
        if s[ids-1] == t[idt-1]:
            dp[ids][idt] =dp[ids-1][idt-1] + 1
        #違っていたら、長い方の文字を採用
        elif s[ids-1] != t[idt-1]:
            if dp[ids][idt-1] >= dp[ids-1][idt]:
                dp[ids][idt] = dp[ids][idt-1]
            else:
                dp[ids][idt] = dp[ids-1][idt]
ans = ''
num=dp[-1][-1]
ids = ls;idt=lt
while num:
    if dp[ids][idt] == dp[ids][idt-1]:
        idt -= 1
    elif dp[ids][idt] == dp[ids-1][idt]:
        ids -=1
    elif dp[ids][idt] ==dp[ids-1][idt-1] + 1:
        ans += s[ids-1]
        num -=1
        idt -= 1
        ids -=1
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
s= input()
t = input()
ls = len(s)
lt = len(t)
dp = [["" for _ in range(lt+1) ]  for _ in range(ls+1)] #dp[i][j] sがi文字目,tがj文字目まででのLCS
for ids in range(1,ls+1):
    for idt in range(1,lt + 1):
        #一致してたら文字を足す
        if s[ids-1] == t[idt-1]:
            dp[ids][idt] = dp[ids-1][idt-1] + s[ids-1]
        #違っていたら、長い方の文字を採用
        elif s[ids-1] != t[idt-1]:
            if len(dp[ids][idt-1]) >= len(dp[ids-1][idt]):
                dp[ids][idt] = dp[ids][idt-1]
            else:
                dp[ids][idt] = dp[ids-1][idt]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s = [''] + s
t = list(input())
t = [''] + t
dp = [[0] * (len(t)) for _ in range(len(s))]

# dpテーブル作成

for i in range(1, len(s)):
    for j in range(1, len(t)):

        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]) 

answer_len = dp[len(s)-1][len(t)-1]

# dpテーブル逆走
answer = [0] * answer_len
i = len(s) -1
j = len(t) -1

while True:
    if dp[i][j] - dp[i-1][j-1] == 1 and dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] == 1:
        answer[answer_len-1] = s[i]
        answer_len -= 1
        i -= 1
        j -= 1
        if answer[0] != 0:
            break
    elif dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] != 1:
        i -= 1
    elif dp[i][j] - dp[i][j-1] != 1 and dp[i][j] - dp[i-1][j] == 1:
        j -= 1
    else:
        j -= 1

    if j == 0:
        j += 1
        i -= 1
    
    if i == 0:
        break
 
print(''.join(answer))

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
t = str(input())

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

for i in range(1,len(s)+1):
    for u in range(1,len(t)+1):
        if s[i-1]==t[u-1]:
            dp[u][i]=dp[u-1][i-1]+1
        else:
            dp[u][i]=max(dp[u-1][i],dp[u][i-1])
lenth=dp[-1][-1]
i=len(s)
j=len(t)
ans=""
while lenth>0:
    if s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        i-=1
        j-=1
        lenth-=1
    elif dp[j][i]==dp[j-1][i]:
        j-=1
    else:
        i-=1
    lenth=dp[j][i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def input(): return sys.stdin.readline().rstrip()


S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
# dp[i][j] := i,j までの最大のもの。(length)
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]

            elif dp[i+1][j] < dp[i][j+1]:
                dp[i+1][j+1] = dp[i][j+1]
X, Y = len(S), len(T)
ans = []
while dp[X][Y]:
    if S[X-1] == T[Y-1]:
        ans.append(S[X-1])
        X -= 1
        Y -= 1
    else:
        if dp[X-1][Y] >= dp[X][Y-1]:
            X -= 1
        else:
            Y -= 1
            continue
ans.reverse()
print("".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(6009)
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
def lcs(i,j):
	if dp[i][j]!=0:
		return dp[i][j]
	if i*j==0:
		return 0
	if s[i-1]==t[j-1]:
		r=lcs(i-1,j-1)+1
	else:
		r=max(lcs(i,j-1),lcs(i-1,j))
	dp[i][j]=r
	return r
		
		

lcs(n,m)

i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])

Submission status: Time Limit Exceeded

Solution code:

s=input()
n=len(s)
t=input()
m=len(t)
dp=[["" for i in range(m)] for j in range(n)]

for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			if j==0 or i==0:
				x=""
			else:
				x=dp[i-1][j-1]
			dp[i][j]=x+s[i]
		else:
			if i==0:
				a=""
			else:
				a=dp[i-1][j]
			if j==0:
				b=""
			else:
				b=dp[i][j-1]
			if len(a)>len(b):
				dp[i][j]=a
			else:
				dp[i][j]=b
print(dp[n-1][m-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(6009)
s=input()
n=len(s)
t=input()
m=len(t)
dp=[[0 for i in range(m)] for j in range(n)]
def lcs(x,y):
	
	if min(x,y)<=-1:
		return ""
	if dp[x][y]!=0:
		return dp[x][y]
	if s[x]==t[y]:
		dp[x][y]=lcs(x-1,y-1)+s[x]
		return dp[x][y]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		dp[x][y]=a
		return a
	else:
		dp[x][y]=b
		return b
print(lcs(n-1,m-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(6009)
from collections import defaultdict
dp=defaultdict(lambda:0)

s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	
	if min(x,y)<=-1:
		return ""
	if dp[(x,y)]!=0:
		return dp[(x,y)]
	if s[x]==t[y]:
		dp[(x,y)]=lcs(x-1,y-1)+s[x]
		return dp[(x,y)]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		dp[(x,y)]=a
		return a
	else:
		dp[(x,y)]=b
		return b
print(lcs(n-1,m-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(6009)
from collections import defaultdict
dp=defaultdict(lambda:"")

s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	if min(x,y)<=-1:
		return ""
	if dp[(x,y)]!="":
		return dp[(x,y)]
	if s[x]==t[y]:
		dp[(x,y)]=lcs(x-1,y-1)+s[x]
		return dp[(x,y)]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		dp[(x,y)]=a
		return a
	else:
		dp[(x,y)]=b
		return b
print(lcs(n-1,m-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(6009)
s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	if min(x,y)<=-1:
		return ""
	if s[x]==t[y]:
		return lcs(x-1,y-1)+s[x]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		return a
	else:
		return b
print(lcs(n-1,m-1))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
import numba as nb 

input  = stdin.readline

@nb.njit()
def lcsdp(s,t):
	dp = [[0 for _ 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):
			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])

	index = dp[-1][-1] 

	lcs = [""] * (index+1) 
	lcs[index] = "" 

	i = len(s) 
	j = len(t)
	while i > 0 and j > 0: 
		if s[i-1] == t[j-1]: 
			lcs[index-1] = s[i-1] 
			i-=1
			j-=1
			index-=1
		elif dp[i-1][j] > dp[i][j-1]: 
			i-=1
		else: 
			j-=1

	return ''.join(lcs) 

s = input()
t = input()
# print(lcs(s,t, len(s)-1, len(t)-1, ''))
print(lcsdp(s,t))

Submission status: Time Limit Exceeded

Solution code:
def lcs(s,t,i,j, an):
	if i < 0 or j <0:
		return 0
	if s[i]  == t[j]:
		return 1 + lcs(s,t,i-1,j-1, s[i]+an)
	else:
		return max(lcs(s,t,i-1,j,an), lcs(s,t,i,j-1, an))

def lcsdp(s,t):
	dp = [[0 for _ 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):
			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])

	index = dp[-1][-1] 

	lcs = [""] * (index+1) 
	lcs[index] = "" 

	i = len(s) 
	j = len(t)
	while i > 0 and j > 0: 
		if s[i-1] == t[j-1]: 
			lcs[index-1] = s[i-1] 
			i-=1
			j-=1
			index-=1
		elif dp[i-1][j] > dp[i][j-1]: 
			i-=1
		else: 
			j-=1

	return ''.join(lcs) 

s = input()
t = input()
# print(lcs(s,t, len(s)-1, len(t)-1, ''))
print(lcsdp(s,t))

Submission status: Time Limit Exceeded

Solution code:
def longest_common_subsequence(S, T):
    LS = len(S); LT = len(T)
    dp = [[0] * (LT + 1) for _ in range(LS + 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][j + 1], dp[i + 1][j])
    return dp
    

def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i and j:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))


s,t=input(), input()
print(reconstruct_LCS(s, t, longest_common_subsequence(s, t)))

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
a=len(s)
b=len(t)
dp=[[[0,[]] for j in range(a+1)] for i in range(b+1)]
for i in range(1,b+1):
    for j in range(1,a+1):
        if s[j-1]==t[i-1]:
            dp[i][j][0]=dp[i-1][j-1][0]+1
            for x in dp[i-1][j-1][1]:
                dp[i][j][1].append(x)
            dp[i][j][1].append(j-1)
        else:
            if dp[i-1][j][0]>=dp[i][j-1][0]:
                dp[i][j][1]=dp[i-1][j][1]
            else:
                dp[i][j][1]=dp[i][j-1][1]
            dp[i][j][0]=max(dp[i-1][j][0],dp[i][j-1][0])
for z in dp[-1][-1][1]:
    print(s[z],end="")

#print(dp[-1][-1])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
a=len(s)
b=len(t)
dp=[[[0,""] for j in range(a+1)] for i in range(b+1)]
for i in range(1,b+1):
    for j in range(1,a+1):
        if s[j-1]==t[i-1]:
            dp[i][j][0]=dp[i-1][j-1][0]+1
            dp[i][j][1]=dp[i-1][j-1][1]+s[j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1][1])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
# LCS(Longest common subsequence)
s = input()
t = input()

def lcs(str1, str2):
    len1, len2 = len(str1), len(str2)
    lcs_dp = [[0]*(len2+1) for i in range(len1+1)]
    for i in range(len1-1, -1, -1):
        for j in range(len2-1, -1, -1):
            r = max(lcs_dp[i+1][j], lcs_dp[i][j+1])
            if str1[i] == str2[j]:
                r = max(r, lcs_dp[i+1][j+1]+1)
            lcs_dp[i][j] = r
    res = []
    i, j = 0, 0
    while i < len1 and j < len2:
        if str1[i] == str2[j]:
            res.append(str1[i])
            i += 1; j += 1
        elif lcs_dp[i][j] == lcs_dp[i+1][j]:
            i += 1
        elif lcs_dp[i][j] == lcs_dp[i][j+1]:
            j += 1
    return ''.join(res)

print(lcs(s, t))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


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


print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)

dp = [["" for i in range(lt+1)] for j in range(ls+1)]

def main(s,t,ls,lt):
    for i in range(ls):
        for j in range(lt):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                if len(dp[i][j+1]) > len(dp[i+1][j]):
                    dp[i+1][j+1] = dp[i][j+1]
                else:
                    dp[i+1][j+1] = dp[i+1][j]
    return dp[ls][lt]

if __name__ == '__main__':
    print(main(s, t,  ls, lt))

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)

dp = [["" for i in range(lt+1)] for j 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] + s[i]
        else:
            if len(dp[i][j+1]) > len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
print(dp[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ls = len(s)
lt = len(t)

dp = [["" for i in range(lt+1)] for j in range(ls+1)]
dp2 = [[0 for i in range(lt+1)] for j 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] + s[i]
            dp2[i+1][j+1] = dp2[i][j] + 1
        else:
            if dp2[i][j+1] > dp2[i+1][j]:
                dp[i+1][j+1] = dp[i][j+1]
                dp2[i+1][j+1] = dp2[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
print(dp[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
st1 = input()
st2 = input()
dp = [[0 for i in range(len(st2)+1)] for i in range(len(st1)+1)]
for i in range(1,len(st1)+1):
    for j in range(1,len(st2)+1):
        if st1[i-1]==st2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    
l1,l2 = len(st1),len(st2)
ans =''
while(l1>0 and l2>0):
    if dp[l1-1][l2]==dp[l1][l2-1] and dp[l1][l2]!=dp[l1-1][l2]:
        ans+=st2[l2-1]
        l2-=1
        l1-=1
    elif dp[l1][l2]==dp[l1][l2-1]:
        l2-=1
    elif dp[l1][l2]==dp[l1-1][l2]:
        l1-=1
    else:
        l2-=1

print(ans[-1::-1])

Submission status: Time Limit Exceeded

Solution code:
st1 = input()
st2 = input()
dp = [[0 for i in range(len(st2)+1)] for i in range(len(st1)+1)]
for i in range(1,len(st1)+1):
    for j in range(1,len(st2)+1):
        if st1[i-1]==st2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    
l1,l2 = len(st1),len(st2)
ans =''
while(l1>=0 and l2>=0):
    if dp[l1-1][l2]==dp[l1][l2-1] and dp[l1][l2]!=dp[l1-1][l2]:
        ans+=st2[l2-1]
        l2-=1
        l1-=1
    elif dp[l1][l2]==dp[l1][l2-1]:
        l2-=1
    elif dp[l1][l2]==dp[l1-1][l2]:
        l1-=1
    else:
        l2-=1

print(ans[-1::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dp(l1,l2,s,t,cache):
  if not l1 or not l2:
    return ''
  elif cache.get((l1,l2)):
    return cache[(l1,l2)]
  else:
    if s[l1-1]==t[l2-1]:
      cache[(l1,l2)]=dp(l1-1,l2-1,s,t,cache)+s[l1-1]
      return cache[(l1,l2)]
    else:
      temp1=dp(l1-1,l2,s,t,cache)
      temp2=dp(l1,l2-1,s,t,cache)
      cache[(l1,l2)]=temp1 if len(temp1)>=len(temp2) else temp2
      return cache[(l1,l2)]
s=input()
t=input()
print(dp(len(s),len(t),s,t,dict()))

Submission status: Time Limit Exceeded

Solution code:
# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )


dp = [[0 for _ in range(3001)] for _ in range(3001)]


def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result)


def solve(S, T):
    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 - 1][j], dp[i][j - 1], dp[i-1][j-1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    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
        else:
            result += S[i-1]
            i -= 1
            j -= 1
    return "".join(reversed(result))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s=str(input())
t=str(input())
n=len(s)
m=len(t)
l=[[0 for i in range(n+1)] for j in range(m+1)]
for i in range(m+1):
    for j in range(n+1):
        if i==0 or j==0:
            l[i][j]=0
        elif t[i-1]==s[j-1]:
            l[i][j]=l[i-1][j-1]+1
        else:
            l[i][j]=max(l[i][j-1],l[i-1][j])
index=l[m][n]
lcs=[""]*(index+1)
lcs[index]=""
i=m
j=n
while i>0 and j>0:
    if t[i-1]==s[j-1]:
        lcs[index-1]=t[i-1]
        i-=1
        j-=1
        index-=1
    elif l[i-1][j]>l[i][j-1]:
        i-=1
    else:
        j-=1
print("".join(lcs))

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[['' for i in range(m)]for i in range(n)]
for i in range(m-1,-1,-1):
    if(s[-1]==t[i]):
        for j in range(i,-1,-1):
            dp[-1][j]=s[-1]
        break
for i in range(n):
    if(t[-1]==s[i]):
        for j in range(i,-1,-1):
            dp[j][-1]=t[-1]
        break
for i in range(n-2,-1,-1):
    for j in range(m-2,-1,-1):
        if(s[i]==t[j]):
            dp[i][j]=s[i]+dp[i+1][j+1]
        else:
            if(len(dp[i+1][j])>len(dp[i][j+1])):
                dp[i][j]=dp[i+1][j]
            else:
                dp[i][j]=dp[i][j+1]
print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )



def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result)

def solve(S, T):
    dp = [['' 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] = max(dp[i-1][j], dp[i][j-1])
                if len(dp[i-1][j]) >= len(dp[i][j-1]):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
            else:
                a = len(dp[i-1][j-1]) + 1
                b = len(dp[i-1][j])
                c = len(dp[i][j-1])
                if a >= b and a >= c:
                    dp[i][j] = dp[i-1][j-1] + S[i-1]
                elif b>=a and b>= c:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    return dp[len(S)][len(T)]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# LCS: Longest common subsequence
# dp[i][j]: Sのi-1番目まで, Tのj-1番目まででの最長共通文字列
# dp[0][0] = 0 長さ0の文字列
# dp[0][1] = 0 長さ1の文字列と長さ0の文字列
# dp[1][0] = 0 長さ0の文字列と長さ1の文字列
# dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (S[i] != T[j])
# dp[i][j] = max(
#                dp[i-1][j-1]+1  (共通文字列を利用する),
#                dp[i-1][j]        (共通文字列を利用しない),
#                dp[i][j-1]        (共通文字列を利用しない),
#            )



def main():
    S = input()
    T = input()

    result = solve(S, T)
    print(result[1])



def solve(S, T):
    dp = [[[0, ''] for _ in range(len(T)+1)] for _ in range(len(S)+1)]
    for i, s in enumerate(S, start=1):
        for j, t in enumerate(T, start=1):
            if s != t:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=lambda x: x[0])
            else:
                a = dp[i-1][j-1][0]
                b = dp[i-1][j][0]
                c = dp[i][j-1][0]
                if a >= b and a >= c:
                    dp[i][j] = [dp[i-1][j-1][0] + 1, dp[i-1][j-1][1] + s]
                elif b>=a and b>= c:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
    return dp[len(S)][len(T)]


if __name__ == "__main__":
    main()