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: Wrong Answer

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

    for i in range(sl):
        for j in range(tl):
            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 = ""
    cnt = dp[sl][tl]
    x = sl
    y = tl
    while x > 0 and y > 0 and cnt > 0:
        if dp[x - 1][y - 1] == dp[x][y] - 1:
            ans = s[x - 1] + ans
            x -= 1
            y -= 1
            cnt -= 1
        elif dp[x][y] == dp[x - 1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y - 1]:
            y -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    for i in range(sl):
        for j in range(tl):
            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 = ""
    cnt = dp[sl][tl]
    x = sl
    y = tl
    while x > 0 and y > 0 and cnt > 0:
        if dp[x - 1][y - 1] == dp[x][y] - 1:
            ans = s[x - 1] + ans
            x -= 1
            y -= 1
            cnt -= 1
        elif dp[x - 1][y - 1] == dp[x - 1][y]:
            x -= 1
        elif dp[x - 1][y - 1] == dp[x][y - 1]:
            y -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 = [INF for _ in range(max(sl, tl) + 1)]
    ans = ["" for _ in range(max(sl, tl) + 1)]
    dp[0] = 0

    for i in range(sl):
        for j in range(tl - 1, -1, -1):
            if s[i] == t[j]:
                idx = bisect.bisect_left(dp, j + 1)
                dp[idx] = j + 1
                ans[idx] = ans[idx - 1] + s[i]
    ans.sort(reverse=True)
    for ai in ans:
        if ai != "":
            print(ai)
            break


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

s = "0"+s
t = "0"+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] == s[j]:
      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]))

num = list(i for i in range(1,ls+1) if dp[lt][i] == dp[lt][i-1]+1)
ans = ""
for n in num:
  ans += s[n]
print(ans)

Submission status: Wrong Answer

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

    while lt != 0 and ls != 0:
        if dp[ls][lt] == dp[ls - 1][lt]:
            ls -= 1
        elif dp[ls][lt] == dp[ls][lt - 1]:
            lt -= 1
        else:
            ls -= 1
            lt -= 1
            txt = txt +s[ls]

    print(txt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# import sys
# input = sys.stdin.readline
s = input()
t = input()
m = len(s)
n = len(t)

D = [[0] * n for i in range(m)]
D[0][0] = int(s[0] == t[0])

for i in range(1, m):
    D[i][0] = D[i-1][0] | int(s[i] == t[0])
for i in range(1, n):
    D[0][i] = D[0][i-1] | int(s[0] == t[i])

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

maxl = max([max(D[i]) for i in range(m)])
# print(maxl)

ans = []
for i in range(m):
    for j in range(n):
        if D[i][j] == maxl:
            r = i
            c = j
            break

while maxl > 0:
    while c >= 0 and D[r][c-1] == maxl:
        c -= 1
    while r >= 0 and D[r-1][c] == maxl:
        r -= 1
    else:
        ans.append(t[c])
        c -= 1
        r -= 1
        maxl -= 1
print("".join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
a=input()
b=input()
dp=[[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]:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])

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

Submission status: Wrong Answer

Solution code:
def LCS(s1,s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    dp = [[0 for i in range(l2+1)] for j in range(l1+1)]

    flag = False
    for i in range(1,l1+1):
        if flag or s1[i-1] == s2[0]:
            dp[i][0] = 1
            isSameFound = True
    
    flag = False
    for j in range(l2+1):
        if flag or s2[j-1] == s1[0]:
            dp[0][j] = 1
            flag = True 

    for i in range(l1):
        for j in range(l2):
            if s1[i] == s2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            dp[i+1][j+1] = max(max(dp[i+1][j+1],dp[i][j+1]),dp[i+1][j])
    
    lcs_str = ''
    i,j = l1,l2
    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:
            lcs_str += s[i-1]
            i -= 1
            j -= 1
    
    return lcs_str[::-1]

s = input()
t = input()
print(LCS(s,t))

Submission status: Wrong Answer

Solution code:
def LCS(s1,s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    dp = [[0 for i in range(l2)] for j in range(l1)]

    flag = False
    for i in range(l1):
        if flag or s1[i] == s2[0]:
            dp[i][0] = 1
            isSameFound = True
    
    flag = False
    for j in range(l2):
        if flag or s2[j] == s1[0]:
            dp[0][j] = 1
            flag = True 

    max_len = 0

    for i in range(l1-1):
        for j in range(l2-1):
            if s1[i+1] == s2[j+1]:
                dp[i+1][j+1] = dp[i][j] + 1
                max_len = max(max_len,dp[i+1][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    
    lcs_str = ''
    i,j = l1-1,l2-1
    while i>=0 and j>=0:
        if s1[i] == s2[j]:
            lcs_str += s1[i]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    
    return lcs_str[::-1]

s = input()
t = input()
print(LCS(s,t))

Submission status: Wrong Answer

Solution code:
def LCS(s1,s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    dp = [[0 for i in range(l2)] for j in range(l1)]

    flag = False
    for i in range(l1):
        if flag or s1[i] == s2[0]:
            dp[i][0] = 1
            isSameFound = True
    
    flag = False
    for j in range(l2):
        if flag or s2[j] == s1[0]:
            dp[0][j] = 1
            flag = True 

    max_len = 0

    for i in range(l1-1):
        for j in range(l2-1):
            if s1[i+1] == s2[j+1]:
                dp[i+1][j+1] = dp[i][j] + 1
                max_len = max(max_len,dp[i][j])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    
    lcs_str = ''
    i,j = l1-1,l2-1
    while i>=0 and j>=0:
        if s1[i] == s2[j]:
            lcs_str += s1[i]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    
    return lcs_str[::-1]

s = input()
t = input()
print(LCS(s,t))

Submission status: Wrong Answer

Solution code:
def LCS(s1,s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return ''
    
    dp = [[0 for i in range(l2)] for j in range(l1)]

    flag = False
    for i in range(l1):
        if flag or s1[i] == s2[0]:
            dp[i][0] = 1
            isSameFound = True
    
    flag = False
    for j in range(l2):
        if flag or s2[j] == s1[0]:
            dp[0][j] = 1
            flag = True 

    max_len = 0

    for i in range(l1-1):
        for j in range(l2-1):
            if s1[i+1] == s2[j+1]:
                dp[i+1][j+1] = max(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])
    
    lcs_str = ''
    i,j = l1-1,l2-1
    while i>=0 and j>=0:
        if s1[i] == s2[j]:
            lcs_str += s1[i]
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
    
    return lcs_str[::-1]

s = input()
t = input()
print(LCS(s,t))

Submission status: Wrong Answer

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

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

# dp[i][j] = Sのi文字目まで、Tの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:
      dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

#for d in dp:
#  print(d)
# 復元
ans = ""
y = len(T)
x = len(S)
while x > 0 and y > 0:
#  print("x",x,"y",y,"ans",ans)
  if dp[x][y] == dp[x - 1][y - 1] + 1:
    ans += S[x - 1]
    x -= 1
    y -= 1
  else:
    x -= 1

print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import itertools

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

for i in range(len(s), 1, -1):
    s_combo = list(itertools.combinations(s, i))
    t_combo = list(itertools.combinations(t, i))
    for j in range(len(s_combo)):
        if t_combo.count(s_combo[j]) > 0:
            print("".join(s_combo[j]))
            exit(0)
print("")

Submission status: Wrong Answer

Solution code:

S=input()
T=input()

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


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

i=t
j=s
arr=[]
while(i>0 and j>0):
  if dp[i][j]-dp[i-1][j-1]==1:
    arr+=[j-1]
    j-=1
    i-=1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
arr.sort()
for i in arr:
  print(S[i],end="")

Submission status: Wrong Answer

Solution code:
def lcs(i,j):
  #print(i,j)
  if solved[j][i]==1:
    
    return dp[j][i]
  else:
    if S[i-1]==T[j-1]:
      
      dp[j][i]=1+lcs(i-1,j-1)
      solved[j][i]=1
    else:
      dp[j][i]=max(lcs(i-1,j),lcs(i,j-1))
      solved[j][i]=1
    return dp[j][i]

S=input()
T=input()

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

#print(lcs(s,t))

for i in range(s+1):
  for j in range(t+1):
    lcs(i,j)
#for i in dp:
#  print(i)

i=t
j=s
arr=[]
while(i>0 and j>0):
  if dp[i][j]-dp[i-1][j-1]==1:
    arr+=[j-1]
    j-=1
    i-=1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
arr.sort()
for i in arr:
  print(S[i],end="")

Submission status: Wrong Answer

Solution code:
def lcs(i,j):
  #print(i,j)
  if solved[j][i]==1:
    
    return dp[j][i]
  else:
    if S[i-1]==T[j-1]:
      dp[j][i]=1+lcs(i-1,j-1)
      solved[j][i]=1
    else:
      dp[j][i]=max(lcs(i-1,j),lcs(i,j-1))
      solved[j][i]=1
    return dp[j][i]

S=input()
T=input()
s=len(S)
t=len(T)
dp=[[0 for i in range(s+1)] for j in range(t+1)]
solved=[[0 for i in range(s+1)] for j in range(t+1)]
for i in range(t+1):
  solved[i][0]=1
for j in range(s+1):
  solved[0][j]=1

#print(lcs(s,t))

for i in range(s+1):
  for j in range(t+1):
    lcs(i,j)
#for i in dp:
#  print(i)
i=t
j=s
arr=[]
while(i>0 and j>0):
  if dp[i][j]-dp[i-1][j-1]==1:
    #print(S[j-1],end=" ")
    arr+=[S[j-1]]
    i-=1
  j-=1
#print(arr)
for i in range(len(arr)-1,-1,-1):
  print(arr[i],end="")

Submission status: Wrong Answer

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 solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

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

    # dp[0][0] が長さの解

    # ここからは復元処理
    res = []
    i = 0; j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
    return "".join(res)

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 = input().strip()
    T = input().strip()
    lcs = solve(S, T)
    print(lcs)
    """
    s = [ord(c) - 97 for c in input()]
    t = [ord(c) - 97 for c in input()]
    dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
    memo = [[None]*(len(t)+1) for i in range(len(s)+1)]
    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: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	s=si()
	t=si()
	n=len(s)
	m=len(t)
	dp=[[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n):
		for j in range(m):
			if i+j==0:
					dp[i][j]=int(s[i]==t[j])
			elif i==0:
				
					dp[i][j]=max([dp[i][j],dp[i][j-1],int(s[i]==t[j])])
			elif j==0:
				dp[i][j]=max([dp[i][j],dp[i-1][j],int(s[i]==t[j])])
			else:
				dp[i][j]=max([dp[i][j],dp[i-1][j-1]+int(s[i]==t[j]),dp[i][j-1],\
					dp[i-1][j]])	
	i=n-1
	j=m-1
	ans=""
	tle=0
	#for ii in dp[:n]:
	#	print(*ii[:m])
	while i>0 or j>0:
		if dp[i][j]==0:
			break
		if i>0 and j>0 and dp[i][j]-dp[i-1][j-1]==1:
			ans+=s[i]
			i-=1
			j-=1
		
		else:
			if i>0:
				i-=1
			elif j>0:	
				j-=1
		tle+=1
		#print(ans,i,j,tle)
		if tle>n+m:
			break
	if dp[i][j]>0:
		ans+=s[0]			
	print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	s=si()
	t=si()
	n=len(s)
	m=len(t)
	dp=[[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n):
		for j in range(m):
			if i+j==0:
					dp[i][j]=int(s[i]==t[j])
			elif i==0:
				
					dp[i][j]=max([dp[i][j],dp[i][j-1],int(s[i]==t[j])])
			elif j==0:
				dp[i][j]=max([dp[i][j],dp[i-1][j],int(s[i]==t[j])])
			else:
				dp[i][j]=max([dp[i][j],dp[i-1][j-1]+int(s[i]==t[j]),dp[i][j-1],\
					dp[i-1][j]])	
	i=n-1
	j=m-1
	ans=""
	tle=0
	#for ii in dp[:n]:
	#	print(*ii[:m])
	while i>0 or j>0:
		if dp[i][j]==0:
			break
		if i>0 and dp[i][j]-dp[i-1][j]==1:
			ans+=s[i]
			i-=1
			j-=1
		elif j>0 and dp[i][j]-dp[i][j-1]==1:
			ans+=t[j]
			j-=1
			i-=1
		else:
			if i>0:
				i-=1
			if j>0:	
				j-=1
		tle+=1
		#print(ans,i,j,tle)
		if tle>n+m:
			break
	if dp[i][j]>0:
		ans+=s[0]			
	print(ans[::-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
from math import *
from itertools import permutations 
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def gi():	
	return [x for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	
def gh():
	sys.stdout.flush()
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)
def bo(i):
	return ord(i)-ord('a')
		


tt=1



while tt>0:
	tt-=1
	s=si()
	t=si()
	n=len(s)
	m=len(t)
	dp=[[0 for i in range(m+1)] for j in range(n+1)]
	for i in range(n):
		for j in range(m):
			if i+j==0:
					dp[i][j]=int(s[i]==t[j])
			elif i==0:
				
					dp[i][j]=max([dp[i][j],dp[i][j-1],int(s[i]==t[j])])
			elif j==0:
				dp[i][j]=max([dp[i][j],dp[i-1][j],int(s[i]==t[j])])
			else:
				dp[i][j]=max([dp[i][j],dp[i-1][j-1]+int(s[i]==t[j]),dp[i][j-1],\
					dp[i-1][j]])	
	i=n-1
	j=m-1
	ans=""
	tle=0
	#for ii in dp[:n]:
	#	print(*ii[:m])
	while i>0 or j>0:
		if dp[i][j]==0:
			break
		if i>0 and dp[i][j]-dp[i-1][j]==1:
			ans+=s[i]
			i-=1
			j-=1
		elif j>0 and dp[i][j]-dp[i][j-1]==1:
			ans+=t[j]
			j-=1
			i-=1
		else:
			if i>0:
				i-=1
			elif j>0:	
				j-=1
		tle+=1
		#print(ans,i,j,tle)
		if tle>n+m:
			break
	if dp[i][j]>0:
		ans+=s[0]			
	print(ans[::-1])

Submission status: Wrong Answer

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

m, n = len(s), len(t)
dp = [['' for i in range(n+1)] for j in range(m+1)]
for i in range(m):
  for j in range(n):
    if s[i] == t[j]:
      if len(dp[i+1][j]) > len(dp[i][j+1]):
        dp[i+1][j+1] = dp[i+1][j] + s[i]
      else:
        dp[i+1][j+1] = dp[i][j+1] + 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: Wrong Answer

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

Submission status: Wrong Answer

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 = list(input())
    t = list(input())

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

    print(dp[(i, j)])

    #print("".join(lcs))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    print(dp[(i, j)])

    #print("".join(lcs))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

dp = [[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:
            dp[i][j] = 0

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



final = dp[m][n]

lcs = ""

i = m
j = n

while i > 0 and j > 0:
    if s[i-1] == t[j-1]:
        lcs += s[i-1]
        i -= 1
        j -= 1
        final -= 1

    elif dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1


print(lcs)

Submission status: Wrong Answer

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(dp[S][T])
if __name__=='__main__':main()

Submission status: Wrong Answer

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: Wrong Answer

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])
        print(dp[i][j], end = ' ')
    print()
st = []
i = len(a)
j = len(b)
while i > 0 and j > 0:
    print(dp[i][j])
    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: Wrong Answer

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

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

print(find(0, 0))

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
aa = [s for s in a]
bb = [s for s in b]
na = len(a)
nb = len(b)

dp = [[0]*(nb) for _ in range(na)]
k = 0
for i in range(na):
    if a[i] == b[0]:
        k = 1
    dp[i][0] = k
k = 0
for i in range(nb):
    if b[i] == a[0]:
        k = 1
    dp[0][i] = k

for i in range(1, na):
    for j in range(1, nb):
        if a[i] == b[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = []
x = na-1
y = nb-1
while x != 0 or y != 0:
    if x-1 == 0 and dp[x][y] == dp[x-1][y]+1:
        ans.append(a[x])
        x = x-1
    elif y-1 == 0 and dp[x][y] == dp[x][y-1]+1:
        ans.append(b[y])
        y = y-1
    elif x-1 > 0 and dp[x][y] == dp[x-1][y]:
        x = x-1
    elif y-1 > 0 and dp[x][y] == dp[x][y-1]:
        y = y-1
    else:
        ans.append(a[x])
        x = max(0, x-1)
        y = max(0, y-1)

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

Submission status: Wrong Answer

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 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]=0
            else:
                if s1[i]==s2[j]:
                    dp[i][j]=1+dp[i+1][j+1]
                else:
                    dp[i][j]=max(dp[i][j+1],dp[i+1][j])
    n=""
    i,j=0,0
    while i<n1 and j<n2:
        if s1[i]==s2[j]:
            n+=s1[i]
            i+1
            j+=1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                i+=1
            else:
                j+=1
    print(n)
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]

def longest_common_subsequence(S, T):
    """compute table dp satisfying: 
    dp[i,j] = LCS(S[:i], T[:j])"""
    LS, LT = len(S), len(T)
    dp = np.zeros((LS + 1, LT + 1), np.int32)
    for n in range(1, LS + 1):
        dp[n, 1:] = dp[n - 1, :-1] + (S[n - 1] == T)  # 左上から
        np.maximum(dp[n], dp[n - 1], out=dp[n])  # 上から
        np.maximum.accumulate(dp[n], out=dp[n])  # 左から
    return dp

dp = longest_common_subsequence(S, T)

answer = []
i, j = len(S), len(T)
while i > 0 and j > 0:
    if dp[i, j] == dp[i - 1, j - 1] + 1:
        answer.append(S[i - 1])
        i, j = i - 1, j - 1
    elif dp[i, j] == dp[i - 1, j]:
        i -= 1
    elif dp[i, j] == dp[i, j - 1]:
        j -= 1
    else:
        raise ValueError

answer = ''.join(reversed(answer))
print(answer)