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:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


sys.setrecursionlimit(10 ** 7)

s = st()
t = st()


n1 = len(s)
n2 = len(t)

@lru_cache(None)
def dp(i, j):
    if i == n1 or j == n2:return ''
    ans = ''

    curr = s[i]
    ind = j
    while j < n2 and t[j] != curr:
        j += 1
    if j != n2:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    j = ind
    ind = i
    curr = t[j]
    while i < n1 and s[i] != curr:
        i += 1
    if i != n1:
        temp = curr + dp(i + 1, j + 1)
        if len(temp) > len(ans):ans = temp
    
    i = ind

    if len(dp(i + 1, j)) > len(ans):ans = dp(i + 1, j)
    if len(dp(i, j + 1)) > len(ans):ans = dp(i, j + 1)
    

    return ans


print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
n=len(S)
m=len(T)
dp=[['']*(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]+S[i-1]
    else:
      if len(dp[i][j-1])>=len(dp[i-1][j]):
        dp[i][j]=dp[i][j-1]
      else:
        dp[i][j]=dp[i-1][j]
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
S=input()
T=input()
n=len(S)
m=len(T)
dp=[['']*(m+1) for i 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]+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[n][m])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
dp = np.zeros((len(s)+1, len(t)+1))

for i in range(len(s)):
    for j in range(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])

l = int(dp[len(s)-1][len(t)-1])
i = len(s)-1
j = len(t)-1
ans = []

while l>0:
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1
print(''.join(ans[::-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
dp = np.zeros((len(s)+1, len(t)+1))

for i in range(len(s)):
    for j in range(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])

l = int(dp[len(s)-1][len(t)-1])
i = len(s)-1
j = len(t)-1
ans = []

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
dp = np.zeros((len(s)+1, len(t)+1))

for i in range(len(s)):
    for j in range(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])

l = int(dp[len(s)-1][len(t)-1])
i = len(s)-1
j = len(t)-1
ans = []

while dp[i][j]:
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1
print(''.join(ans[::-1]))

Submission status: Time Limit Exceeded

Solution code:


s = input()
l_s = len(s)
t = input()
l_t = len(t)

dp = list([0 for _ in range(l_t+1)] for _ in range(l_s+1))

for i in range(l_s):
    for j in range(l_t):
        #dp[i+1][j+1]  = ...
        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][j], dp[i+1][j] , dp[i][j+1])

ans = []
l = dp[-1][-1]
i = l_s
j = l_t
while l != 0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
        l -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ns = len(s)
nt = len(t)

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

for i in range(1,ns+1):
    for j in range(1,nt+1):

        if s[i-1]==t[j-1]:
            dp[i][j] = 1+dp[i-1][j-1]
            # print(i,j,s[i-1],t[j-1],dp[i][j])
        else: dp[i][j] = max(dp[i-1][j],dp[i][j-1])

index = dp[ns][nt] 
lcs = [""] * (index+1) 
lcs[index] = "" 
i = ns 
j = nt 
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
print(''.join(lcs))

# print(dp)
# print(dp[ns][nt])

Submission status: Time Limit Exceeded

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

S = len(s)
T = len(t)

dp = [[0]*(T+1) for _ in range(S+1)]

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

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: 
        S -= 1
        T -= 1
        ans = s[S] + ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getval():
    s = input()
    t = input()
    return s,t

def main(s,t):
    dp = [["" for i in range(len(t)+1)]]
    for i in range(len(s)):
        temp = [""]
        for j in range(len(t)):
            if s[i]==t[j]:
                temp.append("".join([dp[i][j],s[i]]))
            else:
                if len(dp[i][j+1])>len(temp[-1]):
                    temp.append(dp[i][j+1])
                else:
                    temp.append(temp[-1])
        dp.append(temp)
    print(dp[len(s)][len(t)])
                    
if __name__=="__main__":
    s,t = getval()
    main(s,t)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def main():
    s = input()
    t = input()
    len_s = len(s)
    len_t = len(t)
    dp = [[0] * len_t for i in range(len_s)]

    for j in range(len_t):
        if s[0] == t[j]:
            for k in range(j, len_t):
                dp[0][k] = 1
            break

    for i in range(len_s):
        if s[i] == t[0]:
            for k in range(i, len_s):
                dp[k][0] = 1
            break
    
    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])
    length = dp[-1][-1]
    i = len_s - 1
    j = len_t - 1
    ans = ''
    while (length > 0):
        if s[i] == t[j]:
            ans = s[i] + ans
            i -= 1
            j -= 1
            length -= 1
        elif (j > 0 and dp[i][j - 1] == dp[i][j]) or i == 0:
            j -= 1
        else:
            i -= 1
            
    # for d in dp:
    #     print(d)
    
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

sl = len(s)
tl = len(t)
dp = [["" for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

for i in range(1,sl+1):
    for j in range(1,tl+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = "".join([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[sl][tl])

Submission status: Time Limit Exceeded

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

sl = len(s)
tl = len(t)
dp = [["" for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

for i in range(1,sl+1):
    for j in range(1,tl+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[sl][tl])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0 for i in range(1 + m)] for j in range(1 + n)]
word = [["" for i in range(1 + m)] for j in range(1 + n)]
ans = [0, 0]
res=0
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i - 1] == t[j - 1]:
            word[i][j] = word[i - 1][j - 1] + s[i - 1]
            dp[i][j] = dp[i - 1][j - 1] + 1
            if dp[i][j] > res:
                ans = [i, j]
            res = max(res, dp[i][j])
        else:
            if dp[i - 1][j] >= dp[i][j - 1]:
                word[i][j] = word[i - 1][j]
            else:
                word[i][j] = word[i][j - 1]
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
i, j = ans

print(word[i][j])

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()

dp = [[[0, ''] for i in range(len(s2)+1)] for i in range(len(s1)+1)]


for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = dp[i-1][j-1][1] + s1[i-1]
        else:
            if dp[i-1][j][0] > dp[i][j-1][0]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

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

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()

dp = [[[0, ''] for i in range(len(s2)+1)] for i in range(len(s1)+1)]


for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j][0] = dp[i-1][j-1][0]+1
            dp[i][j][1] = dp[i-1][j-1][1] + s1[i-1]
        else:
            if dp[i-1][j][0] > dp[i][j-1][0]:
                dp[i][j] = list(dp[i-1][j])
            else:
                dp[i][j] = list(dp[i][j-1])

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

Submission status: Time Limit Exceeded

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

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

ans=[""]*dp[i][j]
i=len(s)-1
j=len(t)-1
k=dp[i][j]-1
while i>0 and j>0:
    if s[i]==t[j]:
        ans[k]=s[i]
        k-=1
        i-=1
        j-=1
    elif dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1

print("".join(ans))

Submission status: Time Limit Exceeded

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

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

ans_rev=""
i=len(s)-1
j=len(t)-1

while i>0 and j>0:
    if s[i]==t[j]:
        ans_rev+=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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = input()
t = input()
len_t=len(t)
len_s=len(s) 
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):
    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])

ans=""
count=np.max(dp)
pos_s=len_s
pos_t=len_t

while(len(ans)!=count):
  if s[pos_s-1]==t[pos_t-1]:
    ans=s[pos_s-1]+ans
    pos_s=pos_s-1
    pos_t=pos_t-1
  elif dp[pos_s][pos_t-1]>=dp[pos_s-1][pos_t]:
    pos_t=pos_t-1
  elif dp[pos_s][pos_t-1]<dp[pos_s-1][pos_t]:
    pos_s=pos_s-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
dp=[[0]*(len(t)+1) for i 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])
    # print(dp[i])
ans=''
i,j=len(s),len(t)
while i > 0 and j > 0:
  if s[i-1]==t[j-1]:
    ans=s[i-1]+ans
    i=i-1
    j=j-1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
s=input()
t=input()

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

temp_max=-1
start=[len(dp)-1,-1]
for index,item in enumerate(dp[-1]):
    if item[0]>temp_max:
        temp_max=item[0]
        start[1]=index
        
ans=[]
while start!=[0,0]:
    temp=dp[start[0]][start[1]][1:]
    if start[0]-temp[0]==1 and start[1]-temp[1]==1:
        ans.append(s[temp[0]])
    start=temp[:]


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

Submission status: Time Limit Exceeded

Solution code:


# def solve(s,t,n,m,dp):
#     if n<0 or m<0:
#             return ''
#     if dp[n][m]!=-1:
#         return dp[n][m]
#     else:
#         ans=''
#         if s[n]==t[m]:
#             ans=s[n]+solve(s,t,n-1,m-1,dp)
#             dp[n][m]= ans
#         else:
#             s1=solve(s,t,n-1,m,dp)
#             s2=solve(s,t,n,m-1,dp)
#             if len(s1)>len(s2):
#                 ans=s1
#             else:
#                 ans=s2
#             dp[n][m]= ans
#         return dp[n][m]


s=input()
t=input()
dp=[[""]*(len(t)+1) for i 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]+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[i])


# solve(s,t,len(s)-1,len(t)-1,dp)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

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

print(dp[i][j][1])

Submission status: Time Limit Exceeded

Solution code:
def edu_dp_f_lcs():
    s = input()
    t = input()
    slen = len(s)
    tlen = len(t)
    dp = [[0] * (tlen+1) for _ in range(slen+1)]
    for i in range(slen):
        for j in range(tlen):
            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])

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

edu_dp_f_lcs()

Submission status: Time Limit Exceeded

Solution code:
def edu_dp_f_lcs():
    s = input()
    t = input()
    dp = [[''] * (len(t)+1) for _ in range(len(s)+1)]
    for i in range(0, len(s)):
        for j in range(0, len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            elif 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[len(s)][len(t)])


edu_dp_f_lcs()

Submission status: Time Limit Exceeded

Solution code:
# F - LCS
s = input()
t = input()

m = len(s)
n = len(t)

# dp[i][j]: s の i 文字目、 t の j 文字目までを比較したときの LSC の長さ
dp = [[0]*(n+1) for _ in range(m+1)]

# 初期条件
# 0 文字目 (i=0 or j=0) のとき LSC は 0
for i in range(m+1):
    dp[i][0] = 0
for j in range(n+1):
    dp[0][j] = 0

# s の v 文字目について
for v in range(1,m+1):
    # t の w 文字目について
    for w in range(1,n+1):
        # s の v 文字目と t の w 文字目が同じとき
        if s[v-1] == t[w-1]:
            dp[v][w] = dp[v-1][w-1] + 1
        # s の v 文字目と t の w 文字目が異なるとき
        else:
            dp[v][w] = max(dp[v-1][w],dp[v][w-1])

# 文字列を 「復元」
# DP テーブルの値を見ながら、今いるノード (i,j) がどのノードから更新されて来たのかを特定する

# 遡った文字を保持する配列
res = []

# DP テーブルの末端の index
i = m
j = n
while (i>0 and j>0):
    # (i-1, j) -> (i, j) と遷移していた場合 (s[i-1] != t[j-1]) 
    if (dp[i][j] == dp[i-1][j]):
        # DP の遷移を i について 1 遡る
        i -= 1
    else:
        # (i, j-1) -> (i, j) と遷移していた場合 (s[i-1] != t[j-1]) 
        if (dp[i][j] == dp[i][j-1]):
            # DP の遷移を j について 1 遡る
            j -= 1
        # (i-1, j-1) -> (i, j) と遷移していた場合 (s[i-1] == t[j-1]) 
        else:
            # s[i-1] == t[j-1] なので、res.append(t[j-1]) でも良い
            res.append(s[i-1])
            # DP の遷移を遡る
            i -= 1
            j -= 1
            
# res は逆方向から取得したので reverse する
ans = list(reversed(res))
print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
s = input()
n = len(s)
t = input()
m = len(t)

dp = [[0 for i in range(m+1)] for j 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] = max(dp[i][j],dp[i-1][j-1] + 1)
        elif s[i-1] != t[j-1]:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
k = dp[n][m]
p = list(combinations(range(n),k))
if k == 0:
    print()
    exit()
for i in p:
    cou = 0
    for j in range(m):
        if t[j] == s[i[cou]]:
            cou += 1
        if cou == k:
            for l in i:
                print(s[l],end="")
            print()
            exit()

Submission status: Time Limit Exceeded

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

n = len(s)
m = len(t)

dp = [[0 for a in range(3300)] for b in range(3300)]

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

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

rewsna = ""

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:
        rewsna += s[n-1]
        n -= 1
        m -= 1

print(rewsna[::-1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
l1=len(s)
l2=len(t)
dp=[[0 for _ in range(l2+1)] for _ in range(l1+1)]
for i in range(l1+1):
    for j in range(l2+1):
        if i==0 or j==0:
            dp[i][j]=0
        elif s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            if dp[i-1][j]>dp[i][j-1]:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]
# print(dp[l1][l2])
i=l1
j=l2
ans=''
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        ans=s[i-1]+ans
        i-=1
        j-=1
    elif dp[i-1][j]>dp[i][j-1]:
        i-=1
    else:
        j-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
l1=len(s)
l2=len(t)
dp=[['' for _ in range(l2+1)] for _ in range(l1+1)]
for i in range(l1+1):
    for j in range(l2+1):
        if i==0 or j==0:
            dp[i][j]=""
        elif 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[l1][l2])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
m,n=len(s),len(t)
dp=[[0]*(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:
            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]
a,b=m,n
tmp=''
while a and b:
    if s[a-1]==t[b-1]:
        a-=1
        b-=1
        tmp+=s[a]
    elif dp[a][b]==dp[a-1][b]:
        a-=1
    else:
        b-=1
print(tmp[::-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
	s=input()
	t=input()
	M=len(s)
	N=len(t)
	dp=[[0 for i in range(N+1)] for j in range(M+1)]
	lcs = [['' for i in range(N+1)] for j 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
				lcs[i+1][j+1] = lcs[i][j] + s[i]
			else:
				dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
				if dp[i][j+1]< dp[i+1][j]:
					lcs[i+1][j+1] = lcs[i+1][j]
				else:
					lcs[i+1][j+1] = lcs[i][j+1]
	print(lcs[M][N])
main()

Submission status: Time Limit Exceeded

Solution code:
if __name__=='__main__':
	s=input()
	t=input()
	M=len(s)
	N=len(t)
	dp=[[0 for i in range(N+1)] for j in range(M+1)]
	lcs = [['' for i in range(N+1)] for j 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
				lcs[i+1][j+1] = lcs[i][j] + s[i]
			else:
				dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
				if dp[i][j+1]< dp[i+1][j]:
					lcs[i+1][j+1] = lcs[i+1][j]
				else:
					lcs[i+1][j+1] = lcs[i][j+1]
	print(lcs[M][N])

Submission status: Time Limit Exceeded

Solution code:
def lcs(s,t):
    m = len(s)
    n = len(t)

    dp = [[0]*(n+1) for _ 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] = 1+ dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    
    
    substr = ""
    i,j = m,n
    while i>0 and j>0:
        if s[i-1] == t[j-1]:
            substr+=s[i-1]
            i-=1
            j-=1
        elif dp[i][j-1]>dp[i-1][j]:
            j-=1
        else:
            i-=1
    return substr[::-1]
    
    

# s = "abracadabra"
# t = "avadakedavra"
# s = "axyb"
# t = "abyxb"
s = input()
t = input()
print(lcs(s,t))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s=input()
t=input()

 
dp=np.full((len(s)+1,len(t)+1),0)
from numba import njit
 
 
@njit
def process(dp):
    a=len(s)
    b=len(t)
    for i in range(1,1+len(s)):
        for j in range(1,1+len(t)):
            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 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
            res=s[a]+res
    print(res)
            
process(dp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s=input()
t=input()

 
dp=np.full((len(s)+1,len(t)+1),0)

def process(dp):
    a=len(s)
    b=len(t)
    for i in range(1,1+len(s)):
        for j in range(1,1+len(t)):
            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 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
            res=s[a]+res
    print(res)
            
process(dp)

Submission status: Time Limit Exceeded

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

slen = len(s)
tlen = len(t)

dp = [[0 for _ in range(tlen + 1)] for _ 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 dp[i][j] == dp[i - 1][j - 1] + 1:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
        length -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    else: # dp[i][j] == dp[i][j - 1]:
        j -= 1

print(ans)

Submission status: Time Limit Exceeded

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

n = len(s)
m = len(t)

table = [[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]:
            table[i][j] = table[i-1][j-1] + 1
            
        else:
            table[i][j] = max(table[i-1][j], table[i][j-1])

# for i in table:
#    print(*i)

i, j = n-1, m-1
r = ''

while i >= 0 and j >= 0:
    if table[i][j] + 1 == table[i+1][j+1]:
        r += s[i]
    
    i -= 1
    j -= 1

print(r[::-1])

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
arra = ["-"]
arrb = ["-"]
for i in s1:
    arra.append(i)
for i in s2:
    arrb.append(i)
n1 = len(s1)
n2 = len(s2)
temparr = [[] for i in range(n2 + 1)]
dp = [temparr[::] for i in range(n1 + 1)]

for i in range(1, n1 + 1):
    for j in range(1 , n2 + 1):
        #print("i " + str(i) + " j " + str(j))
        if arra[i] != arrb[j]:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = len(dig)
            uppn = len(upp)
            leftn = len(left)
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig[::] 
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp[::]
            else:
                dp[i][j] = left[::]
        else:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dig.append(arra[i])
            #print(dig)
            
            dign = len(dig)
            uppn = len(upp)
            leftn = len(left)
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig[::] 
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp[::]
            else:
                dp[i][j] = left[::]

# for i in dp:
#     print(i) 
print("".join(dp[-1][-1]))

Submission status: Time Limit Exceeded

Solution code:
s1 = input()
s2 = input()
arra = ["-"]
arrb = ["-"]
for i in s1:
    arra.append(i)
for i in s2:
    arrb.append(i)
n1 = len(s1)
n2 = len(s2)
temparr = ["" for i in range(n2 + 1)]
dp = [temparr[::] for i in range(n1 + 1)]

for i in range(1, n1 + 1):
    for j in range(1 , n2 + 1):
        #print("i " + str(i) + " j " + str(j))
        if arra[i] != arrb[j]:
            dig = dp[i -1][j-1]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = len(dig)
            uppn = len(upp)
            leftn = len(left)
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig 
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left
        else:
            dig = dp[i -1][j-1] + arra[i]
            upp = dp[i - 1][j]
            left = dp[i][j - 1]
            dign = len(dig)
            uppn = len(upp)
            leftn = len(left)
            if dign >= uppn and dign >= leftn:
                dp[i][j] = dig 
            elif uppn >= dign and uppn >= leftn:
                dp[i][j] = upp
            else:
                dp[i][j] = left

# for i in dp:
#     print(i) 
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0]*(m+1) for _ 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])
x=dp[-1][-1]
i=n
j=m
ans=""
while x!=0:
  if dp[i][j]==dp[i][j-1]:
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    ans+=s[i-1]
    i-=1
    j-=1
    x-=1
print(ans[::-1])

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(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.append(a[start[0]-1])
    x = dp[start[0]][start[1]][1]
    y = dp[start[0]][start[1]][2]
    start = [x,y]
s.reverse()
print("".join(s))

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.append(a[start[0]-1])
    x = dp[start[0]][start[1]][1]
    y = dp[start[0]][start[1]][2]
    start = [x,y]
s.reverse()
print("".join(s))