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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
si = len(s)
ti = len(t)
S,T = len(s),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] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])



ans = ""
while dp[si][ti]:
    if dp[si][ti] == dp[si - 1][ti - 1] + 1:
        si -= 1
        ti -= 1
        ans = s[si] + ans
    elif dp[si][ti] == dp[si - 1][ti]:
        si -= 1
    else:
        ti -= 1


if len(ans) == 0:
    print("")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
si = len(s)
ti = len(t)
S,T = len(s),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] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])



ans = ""
while ti >= 0 and si >= 0:
    if dp[si][ti] == dp[si - 1][ti - 1] + 1:
        si -= 1
        ti -= 1
        ans = s[si] + ans
    elif dp[si][ti] == dp[si - 1][ti]:
        si -= 1
    else:
        ti -= 1


if len(ans) == 0:
    print("")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
si = len(s)
ti = len(t)
dp = [[0] * (ti + 1) for _ in range(si + 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 = ""
while ti >= 0 and si >= 0:
    if dp[si][ti] == dp[si - 1][ti - 1] + 1:
        si -= 1
        ti -= 1
        ans = s[si] + ans
    elif dp[si][ti] == dp[si - 1][ti]:
        si -= 1
    else:
        ti -= 1


if len(ans) == 0:
    print("")
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
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])


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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
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:
            if dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]

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

print(ans)

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

            
i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('ok')
else:
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ' '

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][j+1], dp[i+1][j])

            
i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('ok')
else:
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

            
i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print()
else:
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ' '

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][j+1], dp[i+1][j])

            
i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print()
else:
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ' '

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][j+1], dp[i+1][j])

            
i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

            
if ls + lt == 0:
  print('ok')
else:
  
  i = ls-1
  j = lt-1
  while (0<=i & 0<=j):
      if s[i] == t[j]:
          answer += s[i]
          i -= 1
          j -= 1
      elif dp[i+1][j+1] == dp[i+1][j]:
          j -= 1
      else:
          i -= 1
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

            
if ls + lt == 0:
  print(' ')
else:
  
  i = ls-1
  j = lt-1
  while (0<=i & 0<=j):
      if s[i] == t[j]:
          answer += s[i]
          i -= 1
          j -= 1
      elif dp[i+1][j+1] == dp[i+1][j]:
          j -= 1
      else:
          i -= 1
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

            
if ls + lt == 0:
  print('')
else:
  
  i = ls-1
  j = lt-1
  while (0<=i & 0<=j):
      if s[i] == t[j]:
          answer += s[i]
          i -= 1
          j -= 1
      elif dp[i+1][j+1] == dp[i+1][j]:
          j -= 1
      else:
          i -= 1
  print(answer[::-1])

Submission status: Wrong Answer

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1

if ls + lt == 0:
  print()
else:
  print(answer[::-1])

Submission status: Wrong Answer

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

dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])

i = ls-1
j = lt-1
while (0<=i & 0<=j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1

print(answer[::-1])

Submission status: Wrong Answer

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

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

memo = [[''] * (lt) for _ in range(ls)]
flag_s, flag_t = False, False
for i in range(max(ls, lt)):
  if i >= ls:
    if t[i] == s[0] and flag_s == False:
      memo[0][i] = memo[0][i-1] + s[0]
      flag_s = True
    else:
      memo[0][i] = memo[0][i-1]
  elif i >= lt:
    if s[i] == t[0] and flag_t == False:
      memo[i][0] = memo[i-1][0] + t[0]
      flag_t = True
    else:
      memo[i][0] = memo[i-1][0]
  else:
    if s[i] == t[0] and flag_t == False:
      memo[i][0] = memo[i-1][0] + t[0]
      flag_t = True
    else:
      memo[i][0] = memo[i-1][0]
      
    if s[0] == t[i] and flag_s == False:
      memo[0][i] = memo[0][i-1] + s[0]
      flag_s = True
    else:
      memo[0][i] = memo[0][i-1]
      
for i in range(1, ls):
  for j in range(1, lt):
    if s[i] == t[j]:
      memo[i][j] = memo[i-1][j-1] + s[i]
    else:
      if len(memo[i][j-1]) > len(memo[i-1][j]):
        memo[i][j] = memo[i][j-1]
      else:
        memo[i][j] = memo[i-1][j]
print(memo[-1][-1])

Submission status: Wrong Answer

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

dp = [[""]*(lt+2)]*(ls+2)
dp2 = [[0]*(lt+2)]*(ls+2)

for i in range(ls):
    flag = 0
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
            dp2[i+1][j+1] = dp2[i][j] + 1
        else:
            if dp2[i][j+1] > dp2[i+1][j]:
                dp[i+1][j+1] = dp[i][j+1]
                dp2[i+1][j+1] = dp2[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
print(dp[ls][lt])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dp(l1,l2,s,t,cache):
  if not l1 or not l2:
    return ''
  elif cache.get((l1,l2)):
    return cache[(l1,l2)]
  else:
    if s[l1-1]==t[l2-1]:
      cache[(l1,l2)]=dp(l1-1,l2-1,s,t,cache)+s[l1-1]
      return cache[(l1,l2)]
    else:
      temp1=dp(l1-1,l2,s,t,cache)
      temp2=dp(l1,l2-1,s,t,cache)
      cache[(l1,l2)]=temp1 if len(temp1)>=len(temp2) else temp2
      return cache[(l1,l2)]
s=input()
t=input()
dp(len(s),len(t),s,t,dict())

Submission status: Wrong Answer

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

dp = [[""]*(lt+2)]*(ls+2)

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

Submission status: Wrong Answer

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)


def solve(S, T):
    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 - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    length = dp[i][j]
    while length > 0:
        if i >= 1 and j >= 1 and dp[i][j] == dp[i - 1][j - 1] + 1:
            result += S[i - 1]
            i -= 1
            j -= 1
            length -= 1
        elif i >= 1 and dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(result))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)


def solve(S, T):
    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 - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i - 1][j], dp[i][j - 1])
    result = ""
    i = len(S)
    j = len(T)
    while i > 1 and j > 1:
        if i >= 1 and j >= 1 and dp[i][j] == dp[i - 1][j - 1] + 1:
            result += S[i - 1]
            i -= 1
            j -= 1
        elif i >= 1 and dp[i][j] == dp[i - 1][j]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(result))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)


def solve(S, T):
    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-1][j], dp[i][j-1])
            else:
                dp[i][j] = max(dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1])
    result = ''
    i = len(S)
    j = len(T)
    while i > 0 and j >0:
        if i >= 1 and j >=1 and dp[i][j] == dp[i-1][j-1] + 1:
            result += S[i-1]
            i -= 1
            j -= 1
        elif i >= 1 and dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def lcs(X, Y, m, n): 
  
    if m == 0 or n == 0: 
       return 0; 
    elif X[m-1] == Y[n-1]: 
       return 1 + lcs(X, Y, m-1, n-1); 
    else: 
       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
X = "AGGTAB"
Y = "GXTXAYB"
print ("Length of LCS is ", lcs(X, Y, len(X), len(Y)))

Submission status: Wrong Answer

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
ans = ''.join(ans)[::-1]
print(ans)

Submission status: Wrong Answer

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:
    if dp[x-1][y] == cnt:
        x -= 1
    elif dp[x][y-1] == cnt:
        y -= 1
    else:
        ans.append(X[x])
        cnt -= 1
ans = ''.join(ans)[::-1]
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[0 for _ in range(y)] for _ in range(x)]

for i in range(x):
	for j in range(y):
		if s[i]==t[j]:
			dp[i][j] = 1+dp[i-1][j-1]
		else:
			dp[i][j] = max(dp[i-1][j],dp[i][j-1])
i = x-1
j = y-1
ans = ''
while i*j!=0:
	if (dp[i][j] == 1 + dp[i-1][j-1]) and (s[i]==t[j]):
		ans = s[i] + ans
		i-=1
		j-=1
			
	else:	
		if dp[i][j] == dp[i-1][j]:
			i-=1
		elif dp[i][j] == dp[i][j-1]:
			j-=1
if dp[0][0]==1:
	ans = s[0] +ans
print(ans)

Submission status: Wrong Answer

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 31/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')


def main():
	s, t = rll()[0], rll()[0]
	m, n = len(s), len(t)
	dp = [[0 for __ in range(n)] for _ in range(m)]
	dp[0][0] = 1 if s[0] == t[0] else 0
	prnt = defaultdict(lambda: None)
	for r in range(1, m):
		dp[r][0] = dp[r-1][0]
		prnt[(r, 0)] = (r-1, 0)
		if s[r] == t[0]:
			dp[r][0] = 1
			prnt[(r, 0)] = None
	for c in range(1, n):
		dp[0][c] = dp[0][c-1]
		prnt[(0, c)] = (0, c-1)
		if s[0] == t[c]:
			dp[0][c] = 1
			prnt[(0, c)] = None
	for r in range(1, m):
		for c in range(1, n):
			if dp[r-1][c] > dp[r][c]:
				prnt[(r, c)] = (r-1, c)
				dp[r][c] = dp[r-1][c]
			else:
				prnt[(r, c)] = (r, c-1)
				dp[r][c] = dp[r][c-1]
			if s[r] == t[c] and 1 + dp[r-1][c-1] > dp[r][c]:
				dp[r][c] = 1 + dp[r-1][c-1]
				prnt[(r, c)] = (r-1, c-1)
	ans = deque()
	curr = (m-1, n-1)
	while curr is not None:
		r, c = curr
		if s[r] == t[c]:
			ans.appendleft(s[r])
		curr = prnt[curr]
	print("".join(x for x in ans))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def solve():
  ans = ''
  S = input()
  T = input()
  n,m = len(S),len(T)
  dp = [[0]*(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]+1
      else:
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
  i,j = n,m
  while i>0 and j>0:
    M = max([dp[i-1][j-1],dp[i][j-1],dp[i-1][j]])
    if dp[i-1][j-1]==M:
      ans = S[i-1]+ans
      i -= 1
      j -= 1
    elif dp[i-1][j]>=dp[i][j-1]:
      i -= 1
    else:
      j -= 1
  return ans
print(solve())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
a=input()
b=input()
dp=[[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[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])
s1=a
s2=b

#print(dp[len(s1)][len(s2)])
x=len(a)
y=len(b)
res=''
#print(dp[len(a)][len(b)])
while x>00 and y>0:
    if a[x-1]==b[y-1]:
        res+=a[x-1]
        x-=1
        y-=1
    elif dp[x][y]==dp[x-1][y]:
        x-=1
    elif dp[x][y]==dp[x][y-1]:
        y-=1
print(res)

Submission status: Wrong Answer

Solution code:
a=input()
b=input()
dp=[[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[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])
s1=a
s2=b

print(dp[len(s1)][len(s2)])
x=len(a)
y=len(b)
res=''
print(dp[len(a)][len(b)])
while x>00 and y>0:
    if a[x-1]==b[y-1]:
        res+=a[x-1]
        x-=1
        y-=1
    elif dp[x][y]==dp[x-1][y]:
        x-=1
    elif dp[x][y]==dp[x][y-1]:
        y-=1
print(res)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict

def count(y1):
    ans1 = 0
    while y1:
        y1 &= y1-1
        ans1 += 1
    return ans1

s,t = stdin.readline().strip(),stdin.readline().strip()
pos = defaultdict(list)
for ind,val in enumerate(t):
    pos[val].append(ind)
dp = [0 for _ in range(len(t))]
maxi = [0 for _ in range(len(t))]
maxiv = [0 for _ in range(len(t))]
x = 1
for val in s:
    for i in pos[val]:
        y = count(maxi[i]|x)
        if maxiv[i] < y:
            dp[i] = maxi[i]|x
            maxiv[i] = y
    maxim=val=0
    for j in range(len(t)):
        if maxiv[j] > maxim:
            maxim = maxiv[j]
            val = dp[j]
        maxi[j] = val
    x <<= 1
ans = bin(maxi[-1])[2:]
lst = []
for i in range(len(ans)-1,-1,-1):
    if int(ans[i]):
        lst.append(s[len(s)-1-i])
print(''.join(lst))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
s,t = stdin.readline().strip(),stdin.readline().strip()
pos = defaultdict(list)
for ind,val in enumerate(t):
    pos[val].append(ind)
dp = [[] for _ in range(len(t))]
maxi = [[] for _ in range(len(t))]
for val in s:
    for i in pos[val]:
        if len(dp[i]) < len(maxi[i])+1:
            dp[i] = maxi[i]+[val]
    maxim = []
    for j in range(len(t)):
        if len(dp[j]) > len(maxim):
            maxim = dp[j]
        maxi[j] = maxim
print(''.join(maxi[-1]))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict
s,t = stdin.readline().strip(),stdin.readline().strip()
pos = defaultdict(list)
for ind,val in enumerate(t):
    pos[val].append(ind)
dp = ['']*len(t)
maxi = ['']*len(t)
for val in s:
    for i in pos[val]:
        if len(dp[i]) < len(maxi[i])+1:
            dp[i] = maxi[i]+val
    curr = 0
    maxim = ''
    for j in range(len(t)):
        if len(dp[j]) > curr:
            curr = len(dp[j])
            maxim = dp[j]
        maxi[j] = maxim
print(maxi[-1])

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 = ""
    x = sl
    y = tl
    while x > 0 and y > 0:
        if dp[x][y] - 1 == dp[x - 1][y - 1]:
            ans = s[x - 1] + ans
            x -= 1
            y -= 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()