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:
#!/usr/bin/env python
import sys
import re
"""
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)
"""

def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))


    s = [ord(c) - 97 for c in input()]
    t = [ord(c) - 97 for c in input()]

    dp = {}
    memo = {}
    for i in range(len(s)+1):
        for j in range(len(t)+1):
            if i == 0 or j == 0:
                dp[(i, j)] = 0
            else:
                if s[i - 1] == t[j - 1]:
                    dp[(i, j)] = dp[(i - 1, j - 1)] + 1
                    memo[(i, j)] = (i - 1, j - 1)
                else:
                    if dp[(i - 1, j)] < dp[(i, j - 1)]:
                        dp[(i, j)] = dp[(i, j - 1)]
                        memo[(i, j)] = (i, j - 1)
                    else:
                        dp[(i, j)] = dp[(i - 1, j)]
                        memo[(i, j)] = (i - 1, j)
   
    lcs = []
    while dp[i, j] > 0:
        i, j = memo[(i, j)]
        if s[i] == t[j]:
            lcs.insert(0, chr(s[i] + 97))

    print("".join(lcs))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict


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

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

print(dp[n][m][::-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = [' ']+list(input())
    t = [' ']+list(input())
    dp = [[' ' for j in range(len(t))] for i in range(len(s))]
    
    for i in range(1,len(s)):
        for j in range(1,len(t)):
            if s[i]==t[j]:
                dp[i][j] = dp[i-1][j-1]+s[i]
            else:
                if len(dp[i-1][j])>len(dp[i][j-1]):
                    tmp = dp[i-1][j]
                else:
                    tmp = dp[i][j-1]
                dp[i][j] = tmp
            
    print(dp[len(s)-1][len(t)-1].replace(' ',''))     


main()

Submission status: Time Limit Exceeded

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

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

    DP = [[0] * (len_t + 1) for _ in range(len_s + 1)]

    for i in range(len_s):
        for j in range(len_t):
            if s[i] == t[j]:
                DP[i + 1][j + 1] = DP[i][j] + 1
            else:
                DP[i + 1][j + 1] = max(DP[i + 1][j], DP[i][j + 1])

    ans = ""
    i = len_s
    j = len_t
    while DP[i][j]:
        if s[i - 1] == t[j - 1]:
            ans += s[i - 1]
            i -= 1
            j -= 1
        else:
            if DP[i - 1][j] > DP[i][j -1]:
                i -= 1
            else:
                j -= 1

    print(ans[::-1])


if __name__ == '__main__':
    main()

exit()

Submission status: Time Limit Exceeded

Solution code:
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][j+1],dp[i+1][j],dp[i+1][j+1],key=len)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(S, T):
    "void()"
    sizeS = len(S)
    sizeT = len(T)
    import numpy as np
    m = np.zeros((sizeS + 1, sizeT + 1))
    for i in range(1, sizeS + 1):
        for j in range(1, sizeT + 1):
            m[i, j] = max(
                m[i - 1, j],
                m[i, j - 1],
                m[i - 1, j - 1] + 1 if S[i - 1] == T[j - 1] else 0
            )
    result = []
    i = sizeS
    j = sizeT
    while i > 0 and j > 0:
        if m[i, j] == m[i - 1, j]:
            i -= 1
        elif m[i, j] == m[i, j - 1]:
            j -= 1
        else:
            result.append(chr(S[i - 1]))
            i -= 1
            j -= 1
    print("".join(reversed(result)))


def main():
    S = input().strip()
    T = input().strip()
    solve(S, T)


def _test():
    """
    >>> solve("axyb", "abyxb")
    axb
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

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

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

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 += t[j-1]
        i -= 1
        j -= 1
   
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
import re
"""
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)
"""

def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    max_value = 0
    max_key = None
    dp = {}
    for i in range(len(s)+1):
        for j in range(len(t)+1):
            if i == 0 or j == 0:
                dp[(i, j)] = 0
            else:
                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)]])

            value = dp[(i, j)]
            if max_value < value:
                max_key = (i, j)
                max_value = value

    if max_key is None:
        print("")
        return

    lcs = []
    i, j = max_key
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            lcs.insert(0, s[i - 1])
            i -= 1
            j -= 1
        else:
            if dp[(i - 1, j)] > dp[(i, j - 1)]:
                i -= 1
            else:
                j -= 1

    print("".join(lcs))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
import re
"""
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)
"""

def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

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

    max_value = 0
    max_key = None
    for key, value in dp.items():
        if max_value < value:
            max_key = key
            max_value = value

    if max_key is None:
        print("")
        return

    lcs = []
    i, j = max_key
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            lcs.insert(0, s[i - 1])
            i -= 1
            j -= 1
        else:
            if dp[(i - 1, j)] > dp[(i, j - 1)]:
                i -= 1
            else:
                j -= 1

    print("".join(lcs))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
def lcs(s, t):
    if s == '' or t == '':
        return ''
    else:
        if s[0] != t[0]:
            lacks = (lcs(s[1:], t))
            lackt = (lcs(s, t[1:]))
            if len(lacks) > len(lackt):
                return lacks
            else:
                return lackt
        else:
            return s[0] + lcs(s[1:], t[1:])
 
s = input()
t = input()
 
print(lcs(s, t))

Submission status: Time Limit Exceeded

Solution code:
#F=>TLE
S=input()
T=input()

dp=[['' for i in range(len(T)+1)] for j in range(len(S)+1)]

for i in range(len(S)):
    for j in range(len(T)):
        if len(dp[i][j+1])>=len(dp[i+1][j]):
            dp[i+1][j+1]=dp[i][j+1]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            
        if S[i]==T[j] and len(dp[i][j])+1>=len(dp[i+1][j+1]):
            dp[i+1][j+1]=dp[i][j]+T[j]
print(dp[len(S)][len(T)])

Submission status: Time Limit Exceeded

Solution code:
#F
S=input()
T=input()
dp=[['' for i in range(len(T)+1)] for j in range(len(S)+1)]

for i in range(len(S)):
    for j in range(len(T)):
        if len(dp[i][j+1])>=len(dp[i+1][j]):
            dp[i+1][j+1]=dp[i][j+1]
        else:
            dp[i+1][j+1]=dp[i+1][j]
            
        if S[i]==T[j]:
            if len(dp[i][j])+1>=len(dp[i+1][j+1]):
                dp[i+1][j+1]=dp[i][j]+T[j]
print(dp[len(S)][len(T)])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s1, s2 = input(), input()
    n, m = len(s1), len(s2)

    dp = []
    for i in range(n + 1):
        dp.append([0] * (m + 1))

    previous = []
    for i in range(n + 1):
        previous.append([None] * (m + 1))

    for row in range(1, n + 1):
        for column in range(1, m + 1):
            sub1, sub2 = s1[:row], s2[:column]

            if sub1[-1] == sub2[-1]:
                dp[row][column] = 1 + dp[row - 1][column - 1]
                previous[row][column] = (row - 1, column - 1)
            else:
                dpUp = dp[row - 1][column]
                dpLeft = dp[row][column - 1]

                if dpUp > dpLeft:
                    dp[row][column] = dpUp
                    previous[row][column] = (row - 1, column)
                else:
                    dp[row][column] = dpLeft
                    previous[row][column] = (row, column - 1)

    lcs = ''
    curr = (n, m)

    while True:
        i, j = curr
        if previous[i][j] == None: break

        if s1[i - 1] == s2[j - 1]:
            lcs = f'{s1[i - 1]}{lcs}'

        curr = previous[i][j]

    print(lcs)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=list(sys.stdin.readline().strip())
    S,T=len(s),len(t)
    dp=[['' for _ in range(T+1)] for _ in range(S+1)]
    for i in range(S):
        for j in range(T):
            if s[i]==t[j]:dp[i+1][j+1]=dp[i][j]+s[i]
            if len(dp[i+1][j+1])<len(dp[i+1][j]):dp[i+1][j+1]=dp[i+1][j] 
            if len(dp[i+1][j+1])<len(dp[i][j+1]):dp[i+1][j+1]=dp[i][j+1] 
    print(dp[S][T])
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
dp = []
for i in range(len(a)+1):
    dp.append([])
    for j in range(len(b) +1):
        if i == 0 or j == 0:
            dp[i].append(0)
        elif a[i-1] == b[j-1]:
            dp[i].append(1 + dp[i-1][j-1])
        else:
            dp[i].append(max(dp[i-1][j], dp[i][j-1]))
st = []
i = len(a)
j = len(b)
while i > 0 and j > 0:
    if dp[i][j] > max(dp[i-1][j], dp[i][j-1]):
        st.append(a[i-1])
        i -= 1
        j -= 1
    elif dp[i-1][j] > dp[i][j-1]:
            i = i-1
    else:
            j = j-1
for i in range(len(st)-1, -1, -1):
    print(st[i], end = '')

Submission status: Time Limit Exceeded

Solution code:
a = input()
b = input()
dp = [[0 for j in range(3001)] for i in range(3001)]
for i in range(1, len(a)+1):
    for j in range(1, len(b) +1):
        if a[i-1] == b[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
st = []
i = len(a)
j = len(b)
while i > 0 and j > 0:
    if dp[i][j] > max(dp[i-1][j], dp[i][j-1]):
        st.append(a[i-1])
        i -= 1
        j -= 1
    elif dp[i-1][j] > dp[i][j-1]:
            i = i-1
    else:
            j = j-1
for i in range(len(st)-1, -1, -1):
    print(st[i], end = '')

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=list(sys.stdin.readline().strip())
    S,T=len(s),len(t)
    dp=[[[''] for _ in range(T+1)] for _ in range(S+1)]
    for i in range(1,S+1):
        for j in range(1,T+1):
            if s[i-1]==t[j-1]:
                dp[i][j]=dp[i-1][j]+[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(''.join(dp[S][T]))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
a = input()
b = input()
dp = [[None for i in range(3001)] for i in range(3001)]
def find(i, j):
    if dp[i][j]:
        return dp[i][j]
    if i == len(a) or j == len(b):
        return ''
    l = str()
    if a[i] == b[j]:
        l += a[i] + find(i+1, j+1)
        dp[i][j] = l
    else:
        l += max(find(i, j+1), find(i+1, j), key = len)
        dp[i][j] = l
    return dp[i][j]

print(find(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
a = input()
b = input()
def find(i, j):
    if i == len(a) or j == len(b):
        return ''
    l = str()
    if a[i] == b[j]:
        l += a[i] + find(i+1, j+1)
    else:
        l += max(find(i, j+1), find(i+1, j), key = len)
    return l

print(find(0, 0))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

s = input()
t = input()


@njit
def f():
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

    for i, ei in enumerate(s, 1):
        for j, ej in enumerate(t, 1):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

    return dp


dp = f()

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

ans = "".join(ans[::-1])
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, ei in enumerate(s, 1):
    for j, ej in enumerate(t, 1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], (dp[i-1][j-1] + 1) * (ei == ej))

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, gettrace
if not gettrace():
    def input():
        return next(stdin)[:-1]
# def input():
#    return stdin.buffer.readline()
def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    for i in range(n1,-1,-1):
        for j in range(n2,-1,-1):
            if i==n1 or j==n2:
                dp[i][j]=""
            else:
                if s1[i]==s2[j]:
                    dp[i][j]=s1[i]+dp[i+1][j+1]
                else:
                    x=dp[i][j+1]
                    y=dp[i+1][j]
                    if len(x)>len(y):
                        dp[i][j]=x
                    else:
                        dp[i][j]=y
    print(dp[0][0])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, gettrace
import sys
sys.setrecursionlimit(100000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y

def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    for i in range(n1,-1,-1):
        for j in range(n2,-1,-1):
            if i==n1 or j==n2:
                dp[i][j]=""
            else:
                if s1[i]==s2[j]:
                    dp[i][j]=s1[i]+dp[i+1][j+1]
                else:
                    x=dp[i][j+1]
                    y=dp[i+1][j]
                    if len(x)>len(y):
                        dp[i][j]=x
                    else:
                        dp[i][j]=y
    print(dp[0][0])
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=""
        else:
            if s1[i]==s2[j]:
                dp[i][j]=s1[i]+dp[i+1][j+1]
            else:
                x=dp[i][j+1]
                y=dp[i+1][j]
                if len(x)>len(y):
                    dp[i][j]=x
                else:
                    dp[i][j]=y
print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, gettrace
import sys
sys.setrecursionlimit(100000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y

def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    print(recursion(s1,s2,0,0,len(s1),len(s2),dp))
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, gettrace
import sys
sys.setrecursionlimit(1000000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y

def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    print(recursion(s1,s2,0,0,len(s1),len(s2),dp))
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y
        

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
print(recursion(s1,s2,0,0,len(s1),len(s2),dp))

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = 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):
        if S[i] == T[j]:
            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])
A = ''
i = s
j = 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:
        A = S[i - 1] + A
        i -= 1
        j -= 1
print(A)

Submission status: Time Limit Exceeded

Solution code:
#!python3

# input
s = input()
t = input()


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

# input
s = input()
t = input()


def main():
    sn, tn = len(s), len(t)
    dp = [[(0, "")] * (tn + 1) for _ in range(sn + 1)]
    for i in range(1, sn + 1):
        for j in range(1, tn + 1):
            if s[i - 1] == t[j - 1]:
                a, b = dp[i - 1][j - 1]
                dp[i][j] = (a + 1, b + s[i - 1])
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = dp[-1][-1][1]
    print(ans)


if __name__ == "__main__":
    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(len(s)):
  for j in range(len(t)):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
len_=dp[len(s)][len(t)]
s_now=len(s)
t_now=len(t)
ans=''
if len_==0:
  print(ans)
  exit()
while len_>0:
  if s[s_now-1]==t[t_now-1]:
    ans=ans+s[s_now-1]
    len_+=-1
    s_now+=-1
    t_now+=-1
    
  else:
    if dp[s_now][t_now]==dp[s_now][t_now-1]:
      t_now=t_now-1
    elif dp[s_now][t_now]==dp[s_now-1][t_now]:
      s_now=s_now-1
ans=ans[::-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 998244353
	limit = 10**18
	ans = 0
	for test in range(tests):
		s = insr()
		t = insr()
		dp = [["" for j in range(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[-1][-1])


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

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

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

Submission status: Time Limit Exceeded

Solution code:
ss, ts = input(), input()

lenS, lenT = len(ss), len(ts)

dp = [[0]*(lenT+1) for _ in range(lenS+1)]
dp[0][0] = 0
for iS, s in enumerate(ss, 1):
    for jT, t in enumerate(ts, 1):
        if s == t:
            dp[iS][jT] = dp[iS-1][jT-1] + 1
        else:
            dp[iS][jT] = max(dp[iS-1][jT], dp[iS][jT-1])

ans = ''
iS, jT = lenS, lenT
while iS*jT:
    if ss[iS-1] == ts[jT-1]:
        ans += ss[iS-1]
        iS, jT = iS-1, jT-1
    elif dp[iS-1][jT] >= dp[iS][jT-1]:
        iS -= 1
    else:
        jT -= 1

print(ans[::-1])

Submission status: Time Limit Exceeded

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


result=''
dp=[[0]*len(t) for _ in range(len(s))]

for i in range(len(s)):
    for j in range(len(t)):
        if i==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i][j-1] if j>=1 else 0
        elif j==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i-1][j]
        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])

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

L=dp[i][j]

while L>=1:
    if i==0 and dp[i][j]==1:
        result+=s[i]
        L-=1
    elif j==0 and dp[i][j]==1:
        result+=t[i]
        L-=1
    elif dp[i][j]>dp[i-1][j]:
        result+=s[i]
        i-=1
        L-=1
    elif dp[i][j]>dp[i][j-1]:
        result+=t[j]
        j-=1
        L-=1
    elif dp[i][j]>dp[i-1][j-1]:
        result+=t[j]
        L-=1
        i-=1
        j-=1
    else:
        i-=1
        j-=1


print(result[::-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

# dp[i][j] = Sをi文字目、Tをj文字目まで進めたときの最長
# S[i] == S[j]のとき
# dp[i][j] = dp[i - 1][j - 1] + 1
# S[i] != S[j]のとき
# dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])

# その際、自分がどこから来たか？を記録する
# dp[i - 1][j] > dp[i][j - 1]であれば
# route[i][j] = (i,j)を記録

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

# dpテーブルの数字を見て復元していく
ans = ""
x = len(S)
y = len(T)
while x != 0 and y != 0:
  if dp[x][y] == dp[x - 1][y]: # x - 1から遷移してきた
    x -= 1
  elif dp[x][y] == dp[x][y - 1]: # y - 1から遷移してきた
    y -= 1
  else:
    ans += S[x - 1]
    x -= 1
    y -= 1

print(ans[::-1])