Buggy python submission (verdict: Time Limit Exceeded):


# def solve(s,t,n,m,dp):
#     if n<0 or m<0:
#             return ''
#     if dp[n][m]!=-1:
#         return dp[n][m]
#     else:
#         ans=''
#         if s[n]==t[m]:
#             ans=s[n]+solve(s,t,n-1,m-1,dp)
#             dp[n][m]= ans
#         else:
#             s1=solve(s,t,n-1,m,dp)
#             s2=solve(s,t,n,m-1,dp)
#             if len(s1)>len(s2):
#                 ans=s1
#             else:
#                 ans=s2
#             dp[n][m]= ans
#         return dp[n][m]


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

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

        else:
            if len(dp[i-1][j])>len(dp[i][j-1]):
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=dp[i][j-1]

    # print(dp[i])


# solve(s,t,len(s)-1,len(t)-1,dp)
print(dp[-1][-1])

Fixed submission:

# Returns length of LCS for X[0..m-1], Y[0..n-1] 
def lcs(X, Y, m, n): 
	L = [[0 for x in range(n+1)] for x in range(m+1)] 

	# Following steps build L[m+1][n+1] in bottom up fashion. Note 
	# that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
	for i in range(m+1): 
		for j in range(n+1): 
			if i == 0 or j == 0: 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1] + 1
			else: 
				L[i][j] = max(L[i-1][j], L[i][j-1]) 

	# Following code is used to print LCS 
	index = L[m][n] 

	# Create a character array to store the lcs string 
	lcs = [""] * (index+1) 
	lcs[index] = "" 

	# Start from the right-most-bottom-most corner and 
	# one by one store characters in lcs[] 
	i = m 
	j = n 
	while i > 0 and j > 0: 

		# If current character in X[] and Y are same, then 
		# current character is part of LCS 
		if X[i-1] == Y[j-1]: 
			lcs[index-1] = X[i-1] 
			i-=1
			j-=1
			index-=1

		# If not same, then find the larger of two and 
		# go in the direction of larger value 
		elif L[i-1][j] > L[i][j-1]: 
			i-=1
		else: 
			j-=1

	print (''.join(lcs))

# Driver program 

s=input()
t=input()
m = len(s) 
n = len(t) 
lcs(s, t, m, n)

Buggy python submission (verdict: Runtime Error):

def solve(s,t,n,m,dp):
    if n<0 or m<0:
            return ''
    if dp[n][m]!=-1:
        return dp[n][m]
    else:
        ans=''
        if s[n]==t[m]:
            ans=s[n]+solve(s,t,n-1,m-1,dp)
            dp[n][m]= ans
        else:
            s1=solve(s,t,n-1,m,dp)
            s2=solve(s,t,n,m-1,dp)
            if len(s1)>len(s2):
                ans=s1
            else:
                ans=s2
            dp[n][m]= ans
        return dp[n][m]


s=input()
t=input()
dp=[[-1]*(len(t)) for i in range(len(s))] 
# print(dp)
solve(s,t,len(s)-1,len(t)-1,dp)
print(dp[-1][-1][::-1])

Fixed submission:

# Returns length of LCS for X[0..m-1], Y[0..n-1] 
def lcs(X, Y, m, n): 
	L = [[0 for x in range(n+1)] for x in range(m+1)] 

	# Following steps build L[m+1][n+1] in bottom up fashion. Note 
	# that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] 
	for i in range(m+1): 
		for j in range(n+1): 
			if i == 0 or j == 0: 
				L[i][j] = 0
			elif X[i-1] == Y[j-1]: 
				L[i][j] = L[i-1][j-1] + 1
			else: 
				L[i][j] = max(L[i-1][j], L[i][j-1]) 

	# Following code is used to print LCS 
	index = L[m][n] 

	# Create a character array to store the lcs string 
	lcs = [""] * (index+1) 
	lcs[index] = "" 

	# Start from the right-most-bottom-most corner and 
	# one by one store characters in lcs[] 
	i = m 
	j = n 
	while i > 0 and j > 0: 

		# If current character in X[] and Y are same, then 
		# current character is part of LCS 
		if X[i-1] == Y[j-1]: 
			lcs[index-1] = X[i-1] 
			i-=1
			j-=1
			index-=1

		# If not same, then find the larger of two and 
		# go in the direction of larger value 
		elif L[i-1][j] > L[i][j-1]: 
			i-=1
		else: 
			j-=1

	print (''.join(lcs))

# Driver program 

s=input()
t=input()
m = len(s) 
n = len(t) 
lcs(s, t, m, n)