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:
a = list(map(str,input()))
b = list(map(str,input()))
#print(a,b)

n1 = len(a)
n2 = len(b)
#print(n1,n2)

mat = [[0 for i in range(n1+1)] for j in range(n2+1)]

for i in range(n1):
    mat[0][i] = 0
for j in range(n2):
    mat[j][0] = 0

for j in range(1,n2+1):
    for i in range(1,n1+1):
        if a[i-1] == b[j-1]:
            mat[j][i] = max(max(mat[j-1][i],mat[j][i-1]),mat[j-1][i-1]+1)
        else:
            mat[j][i] = max(mat[j-1][i],mat[j][i-1])
'''            
for i in range(n1):
    mat[0][i+1] = a[i]
for j in range(n2):
    mat[j+1][0] = b[j]


for j in range(0,n2+1):
    for i in range(0,n1+1):
        print(mat[j][i],end = " ")
    print("")
'''
    
i = n1 
j = n2
n = 0

list_val = []
len_val = mat[-1][-1]
#print(len_val)
while i >= 1 and j >=1 :
    if mat[j][i] == mat[j][i-1]:
        i = i-1
    else:
        list_val.append(a[i-1])
        i = i-1
        j = j-1
        n = n+1 
        if n == len_val:
            break
#print(list_val)
for i in range(len_val):
    print(list_val[i],end = "")

Submission status: Wrong Answer

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

dp = [[0] * len(t) for _ in range(len(s))]
for i in range(len(s)) :
    for j in range(len(t)) :
        if i == 0 or j == 0 :
            continue
            
        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])
ret = ''
i, j = len(s)-1, len(t)-1
while i >= 1 and j >= 1 :
    if dp[i-1][j-1] < dp[i][j] :
        ret += s[i]
        j -= 1
    i -= 1
print(ret[::-1])

Submission status: Wrong Answer

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

dp = [[0] * len(t) for _ in range(len(s))]
for i in range(len(s)) :
    for j in range(len(t)) :
        if i == 0 or j == 0 :
            continue
            
        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])
ret = ''
i, j = len(s)-1, len(t)-1
while i >= 1 and j >= 1 :
    if dp[i-1][j-1] < dp[i][j] :
        ret += s[i]
        j -= 1
    i -= 1
print(ret[::-1])

Submission status: Wrong Answer

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


dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
#dp[s][t]はs文字とt文字までのやつ

for sx in range(len(s)):
    for ty in range(len(t)):
        #sx+1文字目とty+1文字目が同じなら
        if s[sx]==t[ty]:dp[sx+1][ty+1]=dp[sx][ty]+1
        #違うならどっちか一つ削ったのと同じ
        else:dp[sx+1][ty+1]=max(dp[sx+1][ty],dp[sx][ty+1])

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

Submission status: Wrong Answer

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


dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
#dp[s][t]はs文字とt文字までのやつ

for sx in range(len(s)):
    for ty in range(len(t)):
        if s[sx]==t[ty]:dp[sx+1][ty+1]=dp[sx][ty]+1
        dp[sx+1][ty+1]=max(dp[sx+1][ty+1],dp[sx+1][ty],dp[sx][ty+1])

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

Submission status: Wrong Answer

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


dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
#dp[s][t]はs文字とt文字までのやつ

for sx in range(len(s)):
    for ty in range(len(t)):
        if s[sx]==t[ty]:dp[sx+1][ty+1]=dp[sx][ty]+1
        else:dp[sx+1][ty+1]=max(dp[sx+1][ty],dp[sx][ty+1])

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

Submission status: Wrong Answer

Solution code:
s, t = 'd'+input(), 'd'+input()
n, m = len(s)-1, len(t)-1

# 1-indexed

memo = [[0]*(m+1) for i in range(n+1)]
memo[0][0] = 0

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

ans = ""
i, j = n, m
while i != 0 and j != 0:
    if memo[i][j]-1 == memo[i-1][j-1]:
        ans += s[i]
        i -= 1
        j -= 1
    elif memo[i][j] == memo[i-1][j]:
        i -= 1
    elif memo[i][j] == memo[i][j-1]:
        j -= 1

print(ans[::-1])

Submission status: Wrong Answer

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

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

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

print(result)

Submission status: Wrong Answer

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

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

result = ""
currentCount = 0
for i in range(len(str1)):
    for j in range(len(str2)):
        dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
        if str1[i] == str2[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1] ,dp[i][j] + 1)
            if dp[i + 1][j + 1] - 1 == currentCount:
                result += str1[i]
                currentCount += 1

print(result)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
  from builtins import range
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0] * (tlen + 1) for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    for j in range(tlen):
      j1 = j + 1
      dpij = dpi[j]
      if si == t[j]:
        dpi1[j1] = dpij + 1
      else:
        if dpij > dpi[j1]:
          dpi[j1] = dpij
        dpi1[j] = dpij
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Wrong Answer

Solution code:
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    out = ""
    while i != 0 and j != 0:
        if A[i - 1] == B[j - 1]:
            out = A[i - 1] + out
            i -= 1
            j -= 1
        elif C[i][j - 1] > C[i - 1][j]:
            j -= 1
        else:
            i -= 1
    return out

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    print(ret)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("MZJAWXU", "XMJYAUZ") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"
assert lcs("a", "z") == ""

if False:
    import random
    for _ in range(1000):
        q = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        p = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        lcs("".join(q), "".join(p))

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

def main():
  _max = max
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    si = s[i]
    dpi1j = dpi1[0]
    for j in range(tlen):
      j1 = j + 1
      dpi1j1 = dpi1[j1]
      if si == t[j]:
        dpi1[j1] = _max(dpi1j1, dpi[j] + 1, dpi1j, dpi[j1])
      else:
        dpi1[j1] = _max(dpi1j1,             dpi1j, dpi[j1])
      dpi1j = dpi1j1
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Wrong Answer

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

dp = [[None]*lt for _ in range(ls)]

# init
index_t = t.find(s[0]) + 1 if t[0] in t else 0
for j in range(lt):
    if j >= index_t:
        dp[0][j] = 1
    else:
        dp[0][j] = 0

index_s = s.find(t[0]) if t[0] in s else 0
for i in range(ls):
    if i >= index_s:
        dp[i][0] = 1
    else:
        dp[i][0] = 0

# print(dp)

# solve
for i in range(1, ls):
    for j in range(1, lt):
        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])


# restore
l = dp[-1][-1]
res = ''
i, j = ls-1, lt-1
while l > 0 and (i > 0 or j > 0):
    if i > 0 and dp[i-1][j] == l:
        i -= 1
        # print('i')
    elif j > 0 and dp[i][j-1] == l:
        j -= 1
        # print('j')
    elif dp[i-1][j-1] == l-1:
        res += s[i]
        i, j, l = i-1, j-1, l-1
        # print(i, j, l)

## upper left corner
if l == 1:
    res += s[0]

print(res[::-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
  s = input()
  t = input()
  slen = len(s)
  tlen = len(t)
  dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
  for i in range(slen):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    for j in range(tlen):
      dpi1j1 = dpi1[j + 1]
      if s[i] == t[j]:
        dpi1[j + 1] = max(dpi1j1, dpi[j] + 1)
      dpi1[j + 1] = max(dpi1j1, dpi1[j])
      dpi1[j + 1] = max(dpi1j1, dpi[j + 1])
  result = ''
  i = slen
  j = tlen
  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:
      result = s[i - 1] + result
      i -= 1
      j -= 1
  print(result)
main()

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  dpi = dp[i]
  dpi1 = dp[i + 1]
  for j in range(tlen):
    dpi1j1 = dpi1[j + 1]
    if s[i] == t[j]:
      dpi1[j + 1] = max(dpi1j1, dpi[j] + 1)
    dpi1[j + 1] = max(dpi1j1, dpi1[j])
    dpi1[j + 1] = max(dpi1j1, dpi[j + 1])
result = ''
i = slen
j = tlen
while dp[i][j] != 0:
  if dp[i - 1][j - 1] != dp[i][j]:
    result = s[i - 1] + result
    i -= 1
    j -= 1
  else:
    if dp[i - 1][j] == dp[i][j] and i != 0:
      i -= 1
    else:
      j -= 1
print(result)

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

DP = [[0] * len(T) for _ in range(len(S))]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i][j] = DP[max(0, i-1)][max(0, j-1)] + 1
        else:
            DP[i][j] = max(DP[i][j-1], DP[i-1][j])

cnt = DP[-1][-1]

ls = len(S)-1
lt = len(T)-1

ans = ''

while ls >= -1 and lt >= -1:
    if S[ls] == T[lt]:
        ans += S[ls]
        ls -= 1
        lt -= 1
    else:
        if DP[max(0, ls-1)][lt] > DP[ls][max(0, lt-1)]:
            ls -= 1
        else:
            lt -= 1

if S[0] == T[0]:
    ans += S[0]
print(ans[::-1])

Submission status: Wrong Answer

Solution code:
S = input()
T = input()

DP = [[0] * len(T) for _ in range(len(S))]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            DP[i][j] = DP[max(0, i-1)][max(0, j-1)] + 1
        else:
            DP[i][j] = max(DP[i][j-1], DP[i-1][j])

cnt = DP[-1][-1]
ans = []

for i in range(len(S)-1, -1, -1):
    for j in range(len(T)-1, -1, -1):
        if DP[i][j] == cnt and S[i] == T[j]:
            if DP[max(0,i-1)][max(0,j-1)]==DP[i][j]-1 or DP[max(0,i-1)][j]==DP[i][j]-1 or DP[i][max(0,j-1)]==DP[i][j]-1:
                cnt -= 1
                ans.append(S[i])
                break

if S[0] == T[0]:
    ans.append(S[0])

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

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
ls=len(s)
lt=len(t)
dp=[["" for _ in range(lt+1)] for _ in range(ls+1)]

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

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

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]+s[i-1]
        else:
            dp[i][j]=dp[i][j-1] if len(dp[i][j-1])>len(dp[i-1][j]) else dp[i-1][j]
print(dp[ls][lt])

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 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])
result = ''
i = slen
j = tlen
while dp[i][j] != 0:
  if dp[i - 1][j - 1] != dp[i][j]:
    result = s[i - 1] + result
    i -= 1
    j -= 1
  else:
    if dp[i - 1][j] == dp[i][j] and i != 0:
      i -= 1
    else:
      j -= 1
print(result)

Submission status: Wrong Answer

Solution code:
s, t = input(), input()
ls, lt = map(len,[s,t])

cls_list = [ [ 0 for j in range(lt+1) ] for i in range(ls+1) ]

    

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


ans = []
l = cls_list[-1][-1]
y, x = ls,lt
while l != 0:
    if cls_list[y-1][x-1] == cls_list[y][x] - 1:
        y, x = y - 1, x - 1
        l -= 1
        ans.append(t[x])
    else:
        if y != 1:
            if cls_list[y-1][x] > cls_list[y][x-1]:
                y -= 1
            else:
                x -= 1
        else:
            x -= 1

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

Submission status: Wrong Answer

Solution code:
s, t = input(), input()
ls, lt = map(len,[s,t])

cls_list = [ [ 0 for j in range(lt+1) ] for i in range(ls+1) ]

    

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


ans = []
l = cls_list[-1][-1]
y, x = ls,lt
while l != 0:
    if cls_list[y-1][x-1] != cls_list[y][x]:
        y, x = y - 1, x - 1
        l -= 1
        ans.append(s[y])
    else:
        if cls_list[y-1][x] > cls_list[y][x-1]:
            y -= 1
        else:
            x -= 1
print("".join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
s, t = input(), input()
ls, lt = map(len,[s,t])

cls_list = [ [ 0 for j in range(lt+1) ] for i in range(ls+1) ]

    

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


ans = []
l = cls_list[-1][-1]
y, x = ls,lt
while l != 0:

    if cls_list[y-1][x-1] != cls_list[y][x]:
        y, x = y - 1, x - 1
        l -= 1
        ans.append(s[y])
    else:
        y = y - 1
print("".join(ans[::-1]))

Submission status: Wrong Answer

Solution code:

s, t = input(), input()
ls, lt = map(len,[s,t])

cls_list = [ [ 0 for j in range(lt+1) ] for i in range(ls+1) ]

    

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


ans = []
l = cls_list[-1][-1]
y, x = ls,lt
while l != 0:

    if cls_list[y-1][x-1] != cls_list[y][x]:
        y, x = y - 1, x - 1
        l -= 1
        ans.append(s[y])
    else:
        y = y - 1
print("".join(ans))

Submission status: Wrong Answer

Solution code:
s, t = input(), input()
ls, lt = map(len,[s,t])

cls_list = [ [ 0 for j in range(lt+1) ] for i in range(ls+1) ]

    

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

ans = []
for i in range(lt):
    if cls_list[-1][i] != cls_list[-1][i+1]:
        ans.append(t[i])
print("".join(ans))

Submission status: Wrong Answer

Solution code:
def number():
    return int(input())


def space():
    return list(map(int, input().split()))


def seq_space(n):
    return [list(map(int, input().split())) for _ in range(n)]


S = input()
T = input()

DP = [[''] * len(T) for _ in range(len(S))]

ans = ''

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] != T[j]:
            if j == 0:
                DP[i][j] = DP[i-1][j] if i != 0 else ''
            else:
                if i == 0:
                    DP[i][j] = DP[i][j-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]
        else:
            if j == 0:
                DP[i][j] = DP[i-1][j] + S[i] if i != 0 else S[i]
            else:
                if i == 0:
                    DP[i][j] = S[i]
                else:
                    if len(DP[i-1][j]) == len(DP[i][j-1]):
                        DP[i][j] = DP[i-1][j] + S[i]
                    else:
                        DP[i][j] = min(DP[i-1][j], DP[i][j-1], key=lambda x: len(x)) + S[i]
print(DP[-1][-1])

Submission status: Wrong Answer

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

S = ''+input().rstrip()
T = ''+input().rstrip()
DP = [['']*(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] + S[i]
        else:
            DP[i+1][j+1] = max(DP[i+1][j],DP[i][j+1])
print(DP[-1][-1][:-1])

Submission status: Wrong Answer

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

S = input()
T = input()
DP = [[""]*(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] + S[i]
        else:
            DP[i+1][j+1] = max(DP[i+1][j],DP[i][j+1])
print(DP[-1][-1][:-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
s=' '+input().rstrip()
t=' '+input().rstrip()
m=len(s)-1
n=len(t)-1
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=''
while m>0 and n>0:
    if dp[m][n]==dp[m][n-1]:
        n-=1
    elif dp[m][n]==dp[m-1][n]:
        m-=1
    elif dp[m][n]==dp[m-1][n-1]+1:
        ans=ans+s[m]
        m-=1
        n-=1
print(ans)

Submission status: Wrong Answer

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

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

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

i = len(s) - 1
j = len(t) - 1
c = 0
ans = []
ansl = dp[-1][-1]
while (c < ansl):
    if dp[i][j] == dp[i - 1][j - 1] + 1:
        ans.append(s[i])
        i -= 1
        j -= 1
        c += 1
    else:
        if dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
ans.reverse()
print("".join(ans))

Submission status: Wrong Answer

Solution code:
s=input()
t=input()
n=len(s)
m=len(t)
s1=''
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
  for j in range(m+1):
    if i==0 or j==0:
      continue
    if s[i-1]==t[j-1]:
    
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
l=dp[n][m]#ans
i=n#s
j=m#t
for a in range(n,0,-1):
  for b in range(m,0,-1):
    if l==0:
      break
    if dp[a][b]>dp[a][b-1] and dp[a][b]>dp[a-1][b]:
      s1+=s[a-1]
      l-=1
s2=''
for u in range(dp[n][m]-1,-1,-1):
  s2+=s1[u]
print(s2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

ans = ''

ls = len(s)
lt = len(t)

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

print(ans[::-1])

Submission status: Wrong Answer

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