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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
s=SI()
t=SI()
a=len(s)
b=len(t)
dp=[[0]*(a+1) for i in range(b+1)]
for i in range(1,b+1):
    for j in range(1,a+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])
ans=[]
i,j=b,a
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        ans.append(s[j-1])
        i -= 1
        j -= 1

for x in list(reversed(ans)):
    print(x,end="")

Solution (Python):

s = input()
t = input()

def lcs(str1, str2):
    len1, len2 = len(str1), len(str2)
    lcs_dp = [[0]*(len2+1) for i in range(len1+1)]
    for i in range(len1-1, -1, -1):
        for j in range(len2-1, -1, -1):
            r = max(lcs_dp[i+1][j], lcs_dp[i][j+1])
            if str1[i] == str2[j]:
                r = max(r, lcs_dp[i+1][j+1]+1)
            lcs_dp[i][j] = r
    res = []
    i, j = 0, 0
    while i < len1 and j < len2:
        if str1[i] == str2[j]:
            res.append(str1[i])
            i += 1; j += 1
        elif lcs_dp[i][j] == lcs_dp[i+1][j]:
            i += 1
        elif lcs_dp[i][j] == lcs_dp[i][j+1]:
            j += 1
    return ''.join(res)

print(lcs(s, t))

Solution (Python):
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

ans = []

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

print("".join(reversed(ans)))

Solution (Python):
s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

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

Solution (Python):
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()
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[S][T]:
    if dp[S - 1][T] == dp[S][T]:
        S -= 1
    elif dp[S][T - 1] == dp[S][T]:
        T -= 1
    else:
        S -= 1
        T -= 1
        ans = s[S] + ans


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

Solution (Python):
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])

Solution (Python):
s = input()
t = input()
mx = 0
mxp = [-1, -1]
dp = [[0 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 s[i] == t[j]:
			dp[i + 1][j + 1] = 1 + dp[i][j]
		else:
			dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
		if dp[i + 1][j + 1] > mx:
			mx = dp[i + 1][j + 1]
			mxp = [i + 1, j + 1]
if mx == 0:
	print()
else:
	ans = ''
	x = mxp[0]
	y = mxp[1]
	while dp[x][y]:
		if s[x - 1] == t[y - 1]:
			ans += s[x - 1]
			x -= 1
			y -= 1
		else:
			if dp[x - 1][y] > dp[x][y - 1]:
				x -= 1
			else:
				y -= 1
	print(ans[::-1])

Solution (Python):













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], dp[i-1][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 dp[i][j] != 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            result += S[i-1]
            i -= 1
            j -= 1
    return "".join(reversed(result))


if __name__ == "__main__":
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





A = S()
B = S()

def lcs(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

  
  

  
  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)

print(lcs(A,B))

Solution (Python):
import sys
import numpy as np
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def longest_common_subsequence(S, T):
    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
 
def reconstruct_LCS(S, T, dp):
    tmp = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if S[i - 1] == T[j - 1]:
            i, j = i - 1, j - 1
            tmp.append(S[i])
        elif dp[i, j] == dp[i - 1, j]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(tmp))
 
S = np.array(list(readline().decode()), 'U1')[:-1]
T = np.array(list(readline().decode()), 'U1')[:-1]
 
dp = longest_common_subsequence(S, T)
 
print(reconstruct_LCS(S, T, dp))

Solution (Python):
def LCS_iter(s1, s2):
	dp = [[-10000 for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	ans = [['' for i in range(len(s2) + 1)] for i in range(len(s1) + 1)]
	for i in range(len(s2) + 1):
		dp[0][i] = 0
	for i in range(len(s1) + 1):
		dp[i][0] = 0
	i = 1
	j = 1
	while i <= len(s1):
		while j <= len(s2):
			if s1[i - 1] == s2[j - 1]:
				dp[i][j] = 1 + dp[i - 1][j - 1]
				ans[i][j] = 'cross'
			else:
				if dp[i - 1][j] > dp[i][j - 1]:
					dp[i][j] = dp[i - 1][j]
					ans[i][j] = 'up'
				else:
					dp[i][j] = dp[i][j - 1]
					ans[i][j] = 'left'
			j += 1
		i += 1
		j = 1
	i = len(s1)
	j = len(s2)
	s = ''
	while i >= 0 and j >= 0:
		if ans[i][j] == 'cross':
			s += s1[i - 1]
			i -= 1
			j -= 1
		elif ans[i][j] == 'up':
			i -= 1
		else:
			j -= 1
	return s[::-1]
 
 
s1 = input()
s2 = input()
 
print(LCS_iter(s1, s2))

Solution (Python):
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate

input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]

MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(A,B,m,n,dp):
    for i in range(1,m+1):
        for j in range(1,n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp
                
def longestsub(A,B):
    m = len(A)
    n = len(B)
    if m==0 or n==0:
        return ""
    temp = [0]*(n+1)
    dp = [temp.copy() for i in range(m+1)]
    d = fun(A,B,m,n,dp)
    i= m;j = n;Ans = ""
    while i>0 and j>0:
        if A[i-1] == B[j-1]:
            Ans += A[i-1]
            i-=1;j-=1
        else:
            a = d[i][j-1] ; b =d[i-1][j]
            if a > b:
                j-=1
            else:
                i-=1
    return Ans[::-1]

A = input()
B = input()
print(longestsub(A,B))

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq

s = "0" + input()
t = "1" + input()

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

dp = [[0]*(m) for i in range(n)]

for i in range(n):
    dp[i][0] = 0
for j in range(m):
    dp[0][j] = 0

for i in range(1,n):
    for j in range(1,m):
        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 = ""
i = n-1
j = m-1
len = dp[n-1][m-1]

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

print(ans[::-1])

Solution (Python):
import sys

input = sys.stdin.readline

S = input()
T = input()


def chmax(a, b):
    if a >= b:
        return a
    else:
        return b


def lcs(s, t):
    dp = [[0 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 S[i] == T[j]:
                dp[i + 1][j + 1] = chmax(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = chmax(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = chmax(dp[i + 1][j + 1], dp[i][j + 1])
    ans = ''
    i = len(S)
    j = len(T)
    while (i > 0 and j > 0):
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ans += s[i - 1]
            i -= 1
            j -= 1

    print(ans[::-1])


lcs(S, T)

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

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

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

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

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

for i in range(x):
	for j in range(y):
		if s[i]==t[j]:
			dp[i+1][j+1] = 1+dp[i][j]
		else:
			dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
i = x
j = y
ans = ''
while i*j!=0:
	if (dp[i][j] == 1 + dp[i-1][j-1]) and (s[i-1]==t[j-1]):
		ans = s[i-1] + 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

print(ans)

Solution (Python):
s = input()
t = input()
length_s = len(s)
length_t = len(t)


dp = [[0] * 3005 for _ in range(3005)]



for i in range(length_s):
    for j in range(length_t):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])


res = ""
i = length_s
j = length_t
while i > 0 and j > 0:
    
    if dp[i][j] == dp[i-1][j]:
        i -= 1 
    
    
    elif dp[i][j] == dp[i][j-1]:
        j -= 1 

    
    else:
        
        res = s[i-1] + res
        i -= 1
        j -= 1

print(res)

Solution (Python):




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 s[j - 1] == t[i - 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])

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

Solution (Python):
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
	for r in range(1, m):
		dp[r][0] = max(dp[r-1][0], 1 if s[r] == t[0] else 0)
	for c in range(1, n):
		dp[0][c] = max(dp[0][c-1], 1 if s[0] == t[c] else 0)
	for r in range(1, m):
		for c in range(1, n):
			dp[r][c] = max(dp[r-1][c], dp[r][c-1])
			if s[r] == t[c]:
				dp[r][c] = max(dp[r][c], 1 + dp[r-1][c-1])
	ans = deque()
	r, c = m-1, n-1
	while r >= 0 and c >= 0:
		if s[r] == t[c]:
			ans.appendleft(s[r])
			r -= 1
			c -= 1
		else:
			U = dp[r-1][c] if r > 0 else NINF
			L = dp[r][c-1] if c > 0 else NINF
			if L >= U:
				c -= 1
			else:
				r -= 1
	print("".join(x for x in ans))
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
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-1][j]==dp[i][j]:
      i -= 1
    elif dp[i][j-1]==dp[i][j]:
      j -= 1
    else:
      ans = S[i-1]+ans
      i -= 1
      j -= 1
  return ans
print(solve())

Solution (Python):
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 and M<dp[i][j]:
      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())

Solution (Python):








s = input()
t = input()

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

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

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

res = ""
i = sl
j = tl  
while i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
        i -= 1

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

    else:
        res = s[i - 1] + res
        i -= 1
        j -= 1

print(res)

Solution (Python):
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


x=len(a)
y=len(b)
res=''

while x>0 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[::-1])

Solution (Python):
s=input()
t=input()
n=len(s)
m=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]:
            if i>0 and j>0:
                dp[i][j]=dp[i-1][j-1]+1
        else:
            if i>0:
                dp[i][j]=max(dp[i][j],dp[i-1][j])
            if j>0:
                dp[i][j]=max(dp[i][j],dp[i][j-1])
leng=dp[n][m]
i,j=n,m
ans=""
while leng>0:
    if s[i-1]==t[j-1]:
        ans+=s[i-1]
        i-=1
        j-=1
        leng-=1
    else:
        if dp[i-1][j]==dp[i][j]:
            i-=1
        elif dp[i][j-1]==dp[i][j]:
            j-=1
print(ans[::-1])

Solution (Python):
s=list(input())
t=list(input())
dp=[[0]*(len(s)+1) for i 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]=dp[i-1][j-1] + 1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

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

Solution (Python):
from sys import stdin
s,t = stdin.readline().strip(),stdin.readline().strip()
dp = [[0]*len(s) for _ in range(len(t))]
maxi = [0]*len(s)
for i,val in enumerate(t):
    maxi1 = []
    for x in range(len(s)):
        if s[x] == val:
            dp[i][x] = (0 if x==0 else maxi[x-1])+1
        maxi1.append(max((0 if x==0 else maxi1[x-1]),dp[i][x]))
    for j in range(len(maxi)):
        maxi[j] = max(maxi[j],maxi1[j])
n = max(map(max,dp))
ans,i,j = [],len(t)-1,len(s)-1
while n:
    fl = 0
    for x in range(i,-1,-1):
        for y in range(j,-1,-1):
            if dp[x][y] == n:
                ans.append(s[y])
                fl = 1
                i,j = x-1,y-1
                break
        if fl:
            break
    n -= 1
print(''.join(ans[::-1]))

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

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



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


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




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 s[x - 1] == t[y - 1]:
            ans = s[x - 1] + ans
            x -= 1
            y -= 1
        elif dp[x][y] == dp[x][y - 1]:
            y -= 1
        elif dp[x][y] == dp[x - 1][y]:
            x -= 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



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


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




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 s[x - 1] == t[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()

Solution (Python):
def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    
    
    
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
 
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()

Solution (Python):
s = input()
t = input()
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 = ''
i,j = S,T
while dp[i][j]:
    if dp[i][j] ==dp[i][j-1]:
        j-=1
    elif dp[i][j] == dp[i-1][j]:
        i-=1
    else:
        ans = s[i-1] + ans
        i-=1
        j-=1
print(ans)

Solution (Python):
s1=input()
s2=input()
n1=len(s1)
n2=len(s2)
dp=[[0 for i in range(n2+1)] for j in range(n1+1)] 
for i in range(1,n1+1):
    for j in range(1,n2+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=1+dp[i-1][j-1]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]) 
s=""
i,j=n1,n2
while dp[i][j]:
    if dp[i][j]==dp[i][j-1]:
        j-=1 
    elif dp[i][j]==dp[i-1][j]:
        i-=1 
    else:
        s=s1[i-1]+s
        i-=1 
        j-=1 
print(s)

Solution (Python):
import numpy as np
s = np.array(list(input().rstrip()))
t = np.array(list(input().rstrip()))
ls, lt = len(s), len(t)
dp = np.zeros((ls+1, lt+1), dtype=np.int64)

for i in range(1, ls+1):
  dp[i, 1:] = dp[i-1, :-1] + (s[i-1] == t)
  dp[i] = np.maximum(dp[i], dp[i-1])
  
  dp[i] = np.maximum.accumulate(dp[i])
  
answer = ''
x, y = lt, ls
while x > 0 and y > 0:
  
  if s[y-1] == t[x-1]:
    answer = s[y-1] + answer
    x, y = x-1, y-1
  elif dp[y, x] == dp[y, x-1]:
    x -= 1
  else:
    y -= 1
print(answer)

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

print(main())

Solution (Python):
s = input()
t = input()
s_length = len(s)
t_length = len(t)

dp = [[0]*(t_length + 1) for _ in range(s_length + 1)]
for i in range(s_length):
    for j in range(t_length):
        if s[i]==t[j]:
            dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])
        
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

ans=""
i = s_length
j = t_length
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)

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

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

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

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

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

print(res)

Solution (Python):
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[::-1])


if __name__ == "__main__":
    main()