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:
# 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[1])



def solve(S, T):
    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()

Submission status: Time Limit Exceeded

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(S1,S2,n,m):
    if n == 0 or m == 0:
        return ""
    dp = list2d(n+1,m+1,"")
    for i in range(1,n+1):
        for j in range(1,m+1):
            if S1[i-1] == S2[j-1]:
                dp[i][j] = dp[i-1][j-1] + S1[i-1]
            else:
                a = dp[i-1][j]
                b = dp[i][j-1]
                if len(a) > len(b):
                    dp[i][j] = a
                else:
                    dp[i][j] = b
    return dp[n][m]
    

S1 = input()
S2 = input()
n = len(S1)
m = len(S2)
print(fun(S1,S2,n,m))

Submission status: Time Limit Exceeded

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(S1,S2,n,m):
    if n == 0 or m == 0:
        return ""
    dp = list2d(n+1,m+1,"")
    for i in range(1,n+1):
        for j in range(1,m+1):
            if S1[i-1] == S2[j-1]:
                dp[i][j] = S1[i-1] + dp[i-1][j-1]
            else:
                a = dp[i-1][j]
                b = dp[i][j-1]
                if len(a) > len(b):
                    dp[i][j] = a
                else:
                    dp[i][j] = b
    return dp[n][m][::-1]
    

S1 = input()
S2 = input()
n = len(S1)
m = len(S2)
print(fun(S1,S2,n,m))

Submission status: Time Limit Exceeded

Solution code:
s = input()
s2 = input()
import numpy as np
ans = np.array([[0]*(len(s2)+1)]*(len(s)+1), dtype =  np.int64)
#print(ans)
#print(len(s), len(s2), range(1, len(s2)+1))
for i in range(1, len(s)+1):
    for j in range(1, len(s2)+1):
        #print(s[i-1], s2[j-1], ans, i, j)
        if s[i-1]==s2[j-1]:
            ans[i][j]=ans[i-1][j-1]+1
        else:
            ans[i][j] = max(ans[i-1][j], ans[i][j-1])
ii = -1
jj = -1
val = ""
while True:
    #print(ii, jj)
    if ii==-1*(len(s)+1):
        break
    elif ans[ii][jj]==ans[ii-1][jj]:
        ii-=1
    elif ans[ii][jj]==ans[ii][jj-1]:
        jj-=1
    else:
        val=s[ii]+val
        ii-=1
        jj-=1
print(val)

Submission status: Time Limit Exceeded

Solution code:
X = input()
Y = input()

dp = [[0]*(len(Y)+1) for _ in [0]*(len(X)+1)]

for i, x in enumerate(X):
    i += 1
    for j, y in enumerate(Y):
        j += 1
        dp[i][j] = max(dp[i-1][j-1]+int(x == y),
                       dp[i-1][j], dp[i][j-1])

ans = []
cnt = dp[-1][-1]
x = y = -1
while cnt:
    while dp[x-1][y] == cnt:
        x -= 1
    while dp[x][y-1] == cnt:
        y -= 1
    ans.append(X[x])
    cnt -= 1
    x -= 1
    y -= 1
ans = ''.join(ans)[::-1]
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

word = [""] * dp[-1][-1]

i = n
j = m
index = dp[-1][-1]
while i > 0 and j > 0:
    if s[j-1] == t[i-1]:
        word[index-1] = s[j-1]
        j -= 1
        i -= 1
        index -= 1
    elif dp[i-1][j] > dp[i][j-1]:
        i -= 1 
    else:
        j -= 1

print("".join(word))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = input()
X,Y = len(S),len(T)
L = [[0 for _ in range (Y+1)] for _ in range (X+1)]
for i in range (X):
  for j in range (Y):
    if S[i] == T[j]:
      L[i+1][j+1] = L[i][j]+1
    else:
      L[i+1][j+1] = max(L[i][j+1] , L[i+1][j] , L[i+1][j+1])
K = ''
while X*Y:
  if S[X-1] == T[Y-1]:
    K += S[X-1]
    X -= 1
    Y -= 1
  else:
    if L[X-1][Y] > L[X][Y-1]:
      X -= 1
    else:
      Y -= 1
print(K[::-1])

Submission status: Time Limit Exceeded

Solution code:


a = input()
b = input()
m,n = len(a),len(b)
dp = [ [0]*(n+1) for _ in range(m+1) ]

path = {}
res = ""
for i in range(1,m+1):
    for j in range(1,n+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            path[i,j] = (i-1,j-1)
        else:
            if dp[i-1][j] > dp[i][j-1]:
                path[i,j] = (i-1,j)
                dp[i][j] = dp[i-1][j]
            else:
                path[i,j] = (i,j-1)
                dp[i][j] = dp[i][j-1]
            
#print(dp[-1][-1])#length of the LCS
i,j = (m,n)

while dp[i][j] != 0:
    if a[i-1] == b[j-1]:
        res += a[i-1]
    i,j = path[i,j]

print(res[::-1])

Submission status: Time Limit Exceeded

Solution code:
def solve():
  ans = 0
  S = input()
  T = input()
  n,m = len(S),len(T)
  dp = [['']*(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]+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]
  return dp[-1][-1]
print(solve())

Submission status: Time Limit Exceeded

Solution code:
#import
#import math
#import numpy as np
#= int(input())
#= input()
#= map(int, input().split())
#= [input(), input()]

s = input()
t = input()

sl = len(s)
tl = len(t)

dp = [[0] * (tl + 1) for _ in range(sl + 1)]

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

res = ""
i = sl
j = tl  
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:
        res = s[i - 1] + res
        i -= 1
        j -= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
s, t = input(), input()
n, m = len(s), len(t)
dp = [[0]*-~m for _ in [0]*-~n]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = dp[i][j] + 1 if s[i] == t[j] else max(dp[i][j+1], dp[i+1][j])
R = ""
while n and m:
  if   dp[n][m] == dp[n-1][m]:n -= 1
  elif dp[n][m] == dp[n][m-1]:m -= 1
  else:n -= 1;m -= 1;R = s[n] + R
print(R)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    s = list(input())
    t = list(input())

    sl = len(s)
    tl = len(t)

    dp = [[0 for _ in range(tl + 1)] for __ in range(sl + 1)]
    ans = [["" for _ in range(tl + 1)] for __ in range(sl + 1)]

    for i in range(sl):
        for j in range(tl):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
                ans[i + 1][j + 1] = ans[i][j] + s[i]
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
                if dp[i + 1][j] > dp[i][j + 1]:
                    ans[i + 1][j + 1] = ans[i + 1][j]
                else:
                    ans[i + 1][j + 1] = ans[i][j + 1]

    print(ans[sl][tl])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline

    s = readline()
    t = readline()

    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys


def resolve():
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline

    s = readline()
    t = readline()

    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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] = max2(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][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys


def resolve():
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline

    s = readline()
    t = readline()
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (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] = max2(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][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = ''
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
 
 
def resolve():
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
    
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
    
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1],
                                   dp[i + 1][j],
                                   dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = ''
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res += s[i - 1]
            i -= 1
            j -= 1
    print(res[::-1])
 
 
resolve()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
S,T = len(s),len(t)
dp = [['']*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1] = 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:
def main():
    S = input()
    T = input()
    dp = [[0] * (len(S) + 1) for _ in range(len(T) + 1)]
    for j, t in enumerate(T, 1):
        for i, s in enumerate(S, 1):
            dp[j][i] = max(dp[j - 1][i], dp[j][i - 1], dp[j - 1][i - 1] + 1 if s == t else 0)
    i, j = len(S), len(T)
    R = ''
    while i > 0 and j > 0:
        n = dp[j][i]
        if dp[j - 1][i] == n:
            j -= 1
        elif dp[j][i - 1] == n:
            i -= 1
        elif dp[j - 1][i - 1] == n - 1:
            j -= 1
            i -= 1
            R += T[j]
        else:
            assert False
    return R[::-1]

print(main())

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    s = input()
    t = input()
    dp = [[] for _ in range(len(t))]
    for i in range(len(s)):
        newdp = [[] for _ in range(len(t))]
        for j in range(len(t)):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    newdp[j] = dp[j-1][:]
                    newdp[j].append(s[i])
                else:
                    newdp[j].append(s[i])
            else:
                l = 0
                l2 = 0
                l3 = 0
                if i > 0 and j > 0:
                    l = len(dp[j-1])
                if j > 0:
                    l2 = len(newdp[j-1])
                if i > 0:
                    l3 = len(dp[j])
                if max(l,l2,l3) == 0:
                    continue
                elif max(l,l2,l3) == l:
                    newdp[j] = dp[j-1][:]
                elif max(l,l2,l3) == l2:
                    newdp[j] = newdp[j-1][:]
                else:
                    newdp[j] = dp[j][:]
        dp = copy.deepcopy(newdp)
    print(''.join(dp[-1]))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    t = input()
    dp = [[''] * len(t) for _ in range(len(s))]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                if i > 0 and j > 0:
                    dp[i][j] = dp[i-1][j-1] + s[i]
                else:
                    dp[i][j] += s[i]
            else:
                l = 0
                l2 = 0
                l3 = 0
                if i > 0 and j > 0:
                    l = len(dp[i-1][j-1])
                if j > 0:
                    l2 = len(dp[i][j-1])
                if i > 0:
                    l3 = len(dp[i-1][j])
                if max(l,l2,l3) == 0:
                    dp[i][j] = ''
                elif max(l,l2,l3) == l:
                    dp[i][j] = dp[i-1][j-1]
                elif max(l,l2,l3) == l2:
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = dp[i-1][j]
    if len(dp[-1][-1]) == 0:
        print(' ')
    else:
        print(dp[-1][-1])
main()

Submission status: Time Limit Exceeded

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

dp = [[-1 for _ in range(ls+1)] for _ in range(lt+1)]
dp[0] = [0] * (ls+1)

for i in range(lt+1):
  dp[i][0] = 0

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

res = ""
while ls > 0 and lt > 0:
  if dp[lt][ls] == dp[lt][ls-1]:
    ls -= 1
  elif dp[lt][ls] == dp[lt-1][ls]:
    lt -= 1
  else:
    res = s[ls-1] + res
    ls -= 1
    lt -= 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math


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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    text = []
    dptx = [[""] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] +1
                dptx[i][j] = dptx[i - 1][j - 1] + s[i - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j] >= dp[i][j - 1]:
                    dptx[i][j] = dptx[i - 1][j]
                else:
                    dptx[i][j] = dptx[i][j - 1]

    print(dptx[ls][lt])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math


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


def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    dp = [[0] * (lt + 1) for _ in range(ls + 1)]
    text =[]
    dptx = [[""] * (lt + 1) for _ in range(ls + 1)]
    for i in range(1, ls + 1):
        for j in range(1, lt + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
                if dp[i - 1][j - 1] + 1 >=dp[i - 1][j] and dp[i - 1][j - 1] + 1 >=dp[i][j - 1]:
                    dptx[i][j] =dptx[i-1][j-1] +s[i-1]
                elif dp[i - 1][j - 1] + 1 <=dp[i - 1][j] and dp[i-1][j ] >=dp[i][j - 1]:
                    dptx[i][j] =dptx[i-1][j]
                else:
                    dptx[i][j] =dptx[i][j-1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                if dp[i-1][j ] >=dp[i][j - 1]:
                    dptx[i][j] = dptx[i-1][j]
                else:
                    dptx[i][j] =dptx[i][j-1]

    print(dptx[ls][lt])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

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

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

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

    ans = ""

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


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

# pad a character to the first because i want to count index from 1
s = "." + s; t = "." + t;

a = len(s)
b = len(t)

dp = [['']*(b) for _ in range(a)]
# dp[i][j] is the length of lcs of s[0]s[1]...s[i] and t[0]t[1]...t[j]

for i in range(1, a):
    for j in range(1, b):
        if s[i] == t[j]:
            if len(dp[i][j]) < len(dp[i-1][j-1]) + 1:
                dp[i][j] = dp[i-1][j-1] + s[i]
        else:
            for adja in [[i-1, j-1], [i-1, j], [i, j-1]]:
                if len(dp[i][j]) < len(dp[adja[0]][adja[1]]):
                    dp[i][j] = dp[adja[0]][adja[1]]

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

Submission status: Time Limit Exceeded

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

# pad a character to the first because i want to count index from 1
s = "." + s; t = "." + t;

a = len(s)
b = len(t)

dp = [[0]*(b) for _ in range(a)]
# dp[i][j] is the length of lcs of s[0]s[1]...s[i] and t[0]t[1]...t[j]
last = [[[0]*2 for i1 in range(b)] for i2 in range(a)]

for i in range(1, a):
    for j in range(1, b):
        if s[i] == t[j]:
            if dp[i][j] < dp[i-1][j-1] + 1:
                dp[i][j] = dp[i-1][j-1] + 1
                last[i][j] = [i, j]
        else:
            for adja in [[i-1, j-1], [i-1, j], [i, j-1]]:
                if dp[i][j] < dp[adja[0]][adja[1]]:
                    dp[i][j] = dp[adja[0]][adja[1]]
                    last[i][j] = last[adja[0]][adja[1]]


ans = ''
x, y = last[a-1][b-1]
while x > 0 and y > 0:
    ans += s[last[x][y][0]]
    x, y = last[x][y]
    x -= 1; y -= 1;

#print(*dp, sep = '\n')
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
def lcs():
    s = input()
    t = input()
    # dp = [[0] * (len(s) + 1)] * (len(t) + 1)
    dp = []
    for i in range(len(t) + 1):
        temp = []
        for j in range(len(s) + 1):
            temp.append(0)
        dp.append(temp)
    # print(dp, len(dp), sep="\n")
    just_once = 0
    ans = ""
    for i in range(1, len(dp)):
        for j in range(1, len(dp[0])):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif t[i - 1] == s[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    index = dp[-1][-1]

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

    i = len(dp)-1
    j = len(dp[0])-1
    while i > 0 and j > 0:

        if t[i - 1] == s[j - 1]:
            lcs_algo[index - 1] = t[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_algo))


lcs()

Submission status: Time Limit Exceeded

Solution code:
def lcs():
    s = input()
    t = input()
    # dp = [[0] * (len(s) + 1)] * (len(t) + 1)
    dp = []
    for i in range(len(t) + 1):
        temp = []
        for j in range(len(s) + 1):
            temp.append(0)
        dp.append(temp)
    # print(dp, len(dp), sep="\n")
    just_once = 0
    ans = ""
    for i in range(1, len(dp)):
        for j in range(1, len(dp[0])):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif t[i - 1] == s[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # for v in dp:
    #     print(v)
    #     print()
    i = len(dp) - 1
    j = len(dp[0]) - 1
    while i > 0 and j > 0:
        if s[j-1] == t[i-1]:
            ans = ans + t[i - 1]
            i-=1
            j-=1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    print(ans[::-1],end="")


lcs()

Submission status: Time Limit Exceeded

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

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

for i in range(len(s)-1,-1,-1):
    for j in range(len(t)-1,-1,-1):
        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=dp[0][0]
# print(dp)
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)

Submission status: Time Limit Exceeded

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

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            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=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)

Submission status: Time Limit Exceeded

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

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)


for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            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=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[[] for _ in range(M+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + [S[i]]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print("".join(dp[N][M]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[""]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + S[i]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print(dp[N][M])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
t = input()
S = (len(s)+1)
T = (len(t)+1)

dp = [[0]*T for i in range(S)]

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

# print(dp[len(s)][len(t)])

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

Submission status: Time Limit Exceeded

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

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

data = [[0 for _ in range(n)] for _ in range (m)]

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

i = len(s)
j = len(t)

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

Submission status: Time Limit Exceeded

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

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

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

i = len(s)
j = len(t)

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

Submission status: Time Limit Exceeded

Solution code:
def st (a,b):
    arr=[[0 for i in range(len(a)+1)]for j in range(len(b)+1)]
    for i in range(1,len(b)+1):
        for j in range(1,len(a)+1):
            if a[j-1]==b[i-1]:
                arr[i][j]=arr[i-1][j-1]+1
            else:
                arr[i][j]=max(arr[i-1][j],arr[i][j-1])
    ans=''
    r=len(b)
    c=len(a)
    while r>=1 and c>=1:
        if a[c-1]==b[r-1]:
            ans+=a[c-1]
            r-=1
            c-=1
            continue
        else:
            if arr[r-1][c]>=arr[r][c-1]:
                r-=1
                continue
            else:
                c-=1
                continue
    return ans[::-1]
s1=input()
s2=input()
print (st(s1,s2))