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:
s = input()
t = input()
a = len(s)
b = len(t)
dp = [[0]*(b+1) for _ in range(a+1)]
prev_w = [[0]*(b+1) for _ in range(a+1)]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      if dp[i][j]+1>dp[i+1][j+1]:
        dp[i+1][j+1] = dp[i][j]+1
        prev_w[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]
        prev_w[i+1][j+1] = [i+1,j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
        prev_w[i+1][j+1] = [i,j+1]
#print(dp[a][b])
#print(prev_w[1][3])
ans = ''
while a!=0 and b !=0:
  l = dp[a][b]
  a,b=prev_w[a][b]
  if l>dp[a][b]:
    ans =s[a]+ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
a = len(s)
b = len(t)
dp = [[""]*(b+1) for _ in range(a+1) ]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      if len (dp[i][j]+s[i])>len(dp[i+1][j+1]):
        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[a][b])

Submission status: Time Limit Exceeded

Solution code:
def disp(dp):
    for d in dp:
        print(d)
    print("")

s = input()
t = input()

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

#s のi番目 tのj番目(indexではないまでの共通部分文字列
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        dp[i][j] = max(dp[i][j],dp[i][j-1])

        #print(s[:i])
        #print(t[:j])
        #disp(dp)

i = len(s)
j = len(t)
res = ""
while i > 0 and j > 0:
    #print( "i={} j={}".format(i,j))
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i-1][j-1]+1:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[""] * (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] + s[i - 1]
            elif 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])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[""] * (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] + s[i - 1]
            elif 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])
main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = [[""] * (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] + s[i - 1]
        elif 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
input = sys.stdin.readline
s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#ここまでで、DP配列が完成
#あとはDPの最後から遡る
i = slen
j = tlen
while (i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j]==dp[i][j-1]:
        j -= 1
        continue
    else:
        #print(i,j)
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
ans = ''
slen = len(s)
tlen = len(t)

dp = [[0 for i in range(tlen+1)] for j in range(slen+1)]

for i in range(slen):
    for j in range(tlen):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
#ここまでで、DP配列が完成
#あとはDPの最後から遡る
i = slen
j = tlen
while (i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i -= 1
        continue
    elif dp[i][j]==dp[i][j-1]:
        j -= 1
        continue
    else:
        #print(i,j)
        ans = s[i-1] + ans
        i -= 1
        j -= 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

S = input()
T = input()
ls = len(S)
lt = len(T)
dp = [['' for _ in range(lt+5)] for i in range(ls+5)]
for i in range(ls):
    for j in range(lt):
        if S[i] == T[j]:
            if len(dp[i][j])+1 == max(len(dp[i][j])+1, len(dp[i+1][j]), len(dp[i][j+1])):
                dp[i+1][j+1] = dp[i][j] + S[i]
            elif len(dp[i+1][j]) == max(len(dp[i][j]+1), 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]
        else:
            if len(dp[i+1][j]) == max(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[ls][lt])

Submission status: Time Limit Exceeded

Solution code:
s = ' '+input()
t = ' '+input()
dp = [['']*(len(t)+1) for i in range(len(s)+1)]
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]+s[i]
    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[-2][-2])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

print(ans[::-1])

Submission status: Time Limit Exceeded

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

dp = [['' for _ in range(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]
        elif 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[len(s)][len(t)])

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
m = len(s)
n = len(t)

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

print(ans[m][n])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
trim = lambda s: s[:-1] if s[-1] == "\n" else s
s = trim(stdin.readline())
t = trim(stdin.readline())

dp = defaultdict(lambda: defaultdict(int))
dp[0][0] = 0
for minS in range(0, len(s)):
    for minT in range(0, len(t)):
        dp[minS+1][minT] = max(dp[minS+1][minT], dp[minS][minT])
        dp[minS][minT+1] = max(dp[minS][minT+1], dp[minS][minT])
        if s[minS] == t[minT]:
            dp[minS+1][minT+1] = max(dp[minS+1][minT+1], dp[minS][minT]+1)
            
edgesS = list(dp[len(s)].values())
edgesT = [dp[i][len(t)] for i in range(0, len(s)+1)]
ind = (-1, -1)
ans = ''
if max(edgesS) >= max(edgesT):
    for i in range(0, len(t)+1):
        if dp[len(s)][i] == max(edgesS):
            ind = (len(s), i)
            break
    while (ind[0] != 0) and (ind[1] != 0):
        cur = max(dp[ind[0]-1][ind[1]-1], dp[ind[0]-1][ind[1]], dp[ind[0]][ind[1]-1])
        if (cur == dp[ind[0]-1][ind[1]-1]) and (s[ind[0]-1] == t[ind[1]-1]):
            ind = (ind[0]-1, ind[1]-1)
            ans += s[ind[0]]
        elif cur == dp[ind[0]-1][ind[1]]:
            ind = (ind[0]-1, ind[1])
        else:
            ind = (ind[0], ind[1]-1)
else:
    for i in range(0, len(s)+1):
        if dp[i][len(t)] == max(edgesT):
            ind = (i, len(t))
            break
    while (ind[0] != 0) and (ind[1] != 0):
        cur = max(dp[ind[0]-1][ind[1]-1], dp[ind[0]-1][ind[1]], dp[ind[0]][ind[1]-1])
        if cur == dp[ind[0]-1][ind[1]-1]:
            ind = (ind[0]-1, ind[1]-1)
            ans += s[ind[0]]
        elif cur == dp[ind[0]-1][ind[1]]:
            ind = (ind[0]-1, ind[1])
        else:
            ind = (ind[0], ind[1]-1)
print(ans[::-1])

Submission status: Time Limit Exceeded

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

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

    # # s, t の何文字目が一致しているか
    # dp_table = [[False for _ in range(len(s))] for _ in range(len(t))]
    # for i in range(len(t)):
    #     for j in range(len(s)):
    #         if s[j] == t[i]:
    #             dp_table[i][j] = True

    # print(dp_table)

    # そこまでの最大の長さをもつ文字列
    dp_table_2 = [['' for _ in range(len(s))] for _ in range(len(t))]
    # init:
    ume = ''
    for i in range(len(s)):
        if t[0] == s[i]:
            ume = s[i]
        dp_table_2[0][i] = ume
    ume = ''
    for i in range(len(t)):
        if t[i] == s[0]:
            ume = t[i]
        dp_table_2[i][0] = ume
    # dp:
    for i in range(1, len(t)):
        for j in range(1, len(s)):
            if t[i] == s[j]:
                dp_table_2[i][j] = dp_table_2[i-1][j] if len(dp_table_2[i-1][j]) > len(dp_table_2[i][j-1]) else dp_table_2[i][j-1]
                dp_table_2[i][j] = dp_table_2[i-1][j-1] + s[j] if len(dp_table_2[i-1][j-1] + s[j]) > len(dp_table_2[i][j]) else dp_table_2[i][j]
            else:
                dp_table_2[i][j] = dp_table_2[i-1][j] if len(dp_table_2[i-1][j]) > len(dp_table_2[i][j-1]) else dp_table_2[i][j-1]

    # print(dp_table_2)

    print(dp_table_2[len(t)-1][len(s)-1])

main()

Submission status: Time Limit Exceeded

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

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

    # # s, t の何文字目が一致しているか
    # dp_table = [[False for _ in range(len(s))] for _ in range(len(t))]
    # for i in range(len(t)):
    #     for j in range(len(s)):
    #         if s[j] == t[i]:
    #             dp_table[i][j] = True

    # print(dp_table)

    # そこまでの最大の長さをもつ文字列
    dp_table_2 = [['' for _ in range(len(s))] for _ in range(len(t))]
    # init:
    ume = ''
    for i in range(len(s)):
        if t[0] == s[i]:
            ume = s[i]
        dp_table_2[0][i] = ume
    ume = ''
    for i in range(len(t)):
        if t[i] == s[0]:
            ume = t[i]
        dp_table_2[i][0] = ume
    # dp:
    for i in range(1, len(t)):
        for j in range(1, len(s)):
            if t[i] == s[j]:
                dp_table_2[i][j] = dp_table_2[i-1][j] if len(dp_table_2[i-1][j]) > len(dp_table_2[i][j-1]) else dp_table_2[i][j-1]
                dp_table_2[i][j] = dp_table_2[i-1][j-1] + s[j] if len(dp_table_2[i-1][j-1] + s[j]) > len(dp_table_2[i][j]) else dp_table_2[i][j]
            else:
                dp_table_2[i][j] = dp_table_2[i-1][j] if len(dp_table_2[i-1][j]) > len(dp_table_2[i][j-1]) else dp_table_2[i][j-1]

    # print(dp_table_2)

    print(dp_table_2[len(t)-1][len(s)-1])

main()

Submission status: Time Limit Exceeded

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

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

    # s, t の何文字目が一致しているか
    dp_table = [[False for _ in range(len(s))] for _ in range(len(t))]
    for i in range(len(t)):
        for j in range(len(s)):
            if s[j] == t[i]:
                dp_table[i][j] = True

    # print(dp_table)

    # そこまでの最大の長さをもつ文字列
    dp_table_2 = [['' for _ in range(len(s))] for _ in range(len(t))]
    # init:
    ume = ''
    for i in range(len(s)):
        if dp_table[0][i]:
            ume = s[i]
        dp_table_2[0][i] = ume
    ume = ''
    for i in range(len(t)):
        if dp_table[i][0]:
            ume = t[i]
        dp_table_2[i][0] = ume
    # dp:
    for i in range(1, len(t)):
        for j in range(1, len(s)):
            if dp_table[i][j]:
                dp_table_2[i][j] = dp_table_2[i-1][j] if len(dp_table_2[i-1][j]) > len(dp_table_2[i][j-1]) else dp_table_2[i][j-1]
                dp_table_2[i][j] = dp_table_2[i-1][j-1] + s[j] if len(dp_table_2[i-1][j-1] + s[j]) > len(dp_table_2[i][j]) else dp_table_2[i][j]
            else:
                dp_table_2[i][j] = dp_table_2[i-1][j] if len(dp_table_2[i-1][j]) > len(dp_table_2[i][j-1]) else dp_table_2[i][j-1]

    # print(dp_table_2)

    print(dp_table_2[len(t)-1][len(s)-1])

main()

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[(i+1)%2][j+1] = dp[i%2][j] + s[i]
            else:
                if len(dp[(i+1)%2][j]) >= len(dp[i%2][j+1]):
                    dp[(i+1)%2][j+1] = dp[(i+1)%2][j]
                else:
                    dp[(i+1)%2][j+1] = dp[i%2][j+1]
    return dp[(i+1)%2][n]


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

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[(i+1)%2][j+1] = dp[i%2][j] + s[i]
            else:
                max_l = 0
                max_cand = ""
                for c in [dp[(i+1)%2][j], dp[i%2][j+1]]:
                    if len(c) > max_l:
                        max_l = len(c)
                        max_cand = c
                dp[(i+1)%2][j+1] = max_cand
    return dp[(i+1)%2][n]


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

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + s[i]
            else:
                cand = [dp[i][j], dp[i+1][j], dp[i][j+1]]
                max_l = 0
                max_cand = ""
                for c in cand:
                    if len(c) > max_l:
                        max_l = len(c)
                        max_cand = c
                dp[i+1][j+1] = max_cand
    return dp[m][n]


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

Submission status: Time Limit Exceeded

Solution code:
from io import StringIO


UP = 0
LEFT = 1
LEFTUP = 2


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

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


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

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
dp = [[0 for _ in range(len(s)+1)] for i in range(len(t)+1)]
ans = ""
res = []
for i in range(len(t)+1):
    dp[i][0] = 0
for j in range(len(s)+1):
    dp[0][j] = 0
for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if s[j-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            res.append([i,j])
            
            
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
i,j = len(t),len(s)
while i > 0 and j > 0:
    if [i,j] in res:
        ans += s[j-1]
        i,j = i-1,j-1
        continue
        
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
    
print(ans[::-1])

Submission status: Time Limit Exceeded

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

# LCS
def main():
    s = st()
    t = st()
    slen = len(s)
    tlen = len(t)
    # まず，長さを求める
    # dp[i][j]=(sをi文字目、tをj文字目までみた時の最長共通部分列の長さ)とする
    dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
    # slenはSの長さ、tlenはTの長さとする
    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])  # どっちかの最後の1文字は使わない

    # dp[slen][tlen]が求める長さ

    # 文字復元
    length = dp[slen][tlen]
    i = slen
    j = tlen
    ans = ["" for _ in range(length)]
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans[length - 1] = s[i - 1]
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]: # i文字目が無くても同じ，i文字目は使わない
            i -= 1
        else:
            j -= 1
    print("".join(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# LCS
def main():
    s = st()
    t = st()
    slen = len(s)
    tlen = len(t)
    # まず，長さを求める
    # dp[i][j]=(sをi文字目、tをj文字目までみた時の最長共通部分列の長さ)とする
    dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
    # slenはSの長さ、tlenはTの長さとする
    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])  # どっちかの最後の1文字は使わない

    # dp[slen][tlen]が求める長さ

    # 文字復元
    length = dp[slen][tlen]
    i = slen
    j = tlen
    ans = ""
    while length > 0:
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
            length -= 1
        elif dp[i][j] == dp[i - 1][j]: # i文字目が無くても同じ，i文字目は使わない
            i -= 1
        else:
            j -= 1
    print(ans[::-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = ""

for x in range(2**len(s)):
  tmp = ""
  r1 = -1
  _s = "" 
  for y in range(len(s)):
    if ((x >> y) & 1):
      _s += s[y]
  for i in range(len(_s)):
    for j in range(len(t)):
      if _s[i] == t[j]:
        if j > r1:
          tmp += _s[i]
          r1 = j
          break
  if len(tmp) > len(ans):
    ans = tmp

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [0] * len(t)
lcs = [''] * len(t)
for i in range(1, len(s)) :
    dp_ = [0] * len(t)
    lcs_ = [''] * len(t)
    
    for j in range(1, len(t)) :            
        if s[i] == t[j] :
            dp_[j] = dp[j-1] + 1
            lcs_[j] = lcs[j-1] + s[i]
        else :
            if dp[j] >= dp_[j-1] :
                dp_[j] = dp[j]
                lcs_[j] = lcs[j]
            else :
                dp_[j] = dp_[j-1]
                lcs_[j] = lcs_[j-1]
    dp = dp_
    lcs = lcs_

print(lcs[-1])

Submission status: Time Limit Exceeded

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

dp = [[0] * len(t) for _ in range(len(s))]
lcs = [[''] * len(t) for _ in range(len(s))]
for i in range(len(s)) :
    for j in range(len(t)) :
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
            
        if s[i] == t[j] :
            dp[i][j] = dp[i-1][j-1] + 1
            lcs[i][j] = lcs[i-1][j-1] + s[i]
        else :
            if dp[i-1][j] >= dp[i][j-1] :
                dp[i][j] = dp[i-1][j]
                lcs[i][j] = lcs[i-1][j]
            else :
                dp[i][j] = dp[i][j-1]
                lcs[i][j] = lcs[i][j-1]

print(lcs[-1][-1])

Submission status: Time Limit Exceeded

Solution code:



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

# https://qiita.com/drken/items/03c7db44ccd27820ea0d#f-問題---lcs
S = input().rstrip()
T = input().rstrip()

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

result = ""

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

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

print(result[::-1])

Submission status: Time Limit Exceeded

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

def LCS(S, T):
    lenS, lenT = len(S), len(T)
    lcs_set = [[[] for j in range(lenT + 1)] for i in range(lenS + 1)]
    for i in range(0, lenS + 1):
        lcs_set[i][0].append("")
    for j in range(1, lenT + 1):
        lcs_set[0][j].append("")
    for i in range(1, lenS + 1):
        for j in range(1, lenT + 1):
            if S[i-1] == T[j-1]:
                for x in lcs_set[i-1][j-1]:
                    lcs_set[i][j].append(x + S[i-1])
            else:
                if len(lcs_set[i-1][j][0]) < len(lcs_set[i][j-1][0]):
                    lcs_set[i][j] = lcs_set[i][j-1]
                elif len(lcs_set[i-1][j][0]) > len(lcs_set[i][j-1][0]):
                    lcs_set[i][j] = lcs_set[i-1][j]
                else:
                    lcs_set[i][j] = lcs_set[i-1][j] + lcs_set[i][j-1]
            lcs_set[i][j] = list(set(lcs_set[i][j]))
    return lcs_set[lenS][lenT]

print(LCS(input(), input())[0])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
  from builtins import len, max, range
  readline = stdin.readline
  s = stdin.readline()[:-1]
  t = stdin.readline()[:-1]
  dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
  for i in range(1, len(s) + 1):
    s1i = s[i - 1]
    dpi = dp[i]
    dpi1 = dp[i - 1]
    for j in range(1, len(t) + 1):
      if s1i == t[j - 1]:
        dpi[j] = max(dpi[j], dpi1[j], dpi[j - 1], dpi1[j - 1] + 1)
      else:
        dpi[j] = max(dpi[j], dpi1[j], dpi[j - 1])
  u = []
  while True:
    dpi = dp[i]
    if dpi[j] == 0:
      break
    elif dp[i - 1][j] == dpi[j]:
      i -= 1
    elif dpi[j - 1] == dpi[j]:
      j -= 1
    else:
      u.append(s[i - 1])
      i -= 1
      j -= 1
  print(''.join(u[::-1]))
main()

Submission status: Time Limit Exceeded

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