# Longest Common Subsequence - Dynamic Programming / Two Sequences

Solution case #2 and #3 is the same - instead should be replaced for word2. Also there should be explanation for both top-down and bottom-up strategies.

Here an implementation of the bottom up approach:

def longest_common_subsequence(word1: str, word2: str) → int:

``````dp = [[0]*(len(word1)+1) for _ in range(len(word2)+1)]

for i in range(1, len(word2)+1):
for j in range(1, len(word1)+1):

if word2[i-1] == word1[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]

else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

return dp[-1][-1]
``````

That solution is incomprehensible. I have no idea what it is trying to do. Maybe Leetcode will have a better explanation.

hey, we are reworking the DP section. will have better explanation soon.

but the basic idea is to try all choices: match, skip letter in word1, skip letter in word2 and the rest is the same as dfs on tree

All Python solutions including top-down recursion, memoiation, bottom-up tabulation and space optimization, I hope this can help you understand the path of algorithm improvement

``````# # S1 - Top-down recursion, TC = (2**M) * (2**N), SC = M + N, LTE
# class Solution:
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         def f(i, j, s1, s2):
#             if i < 0 or j < 0:
#                 return 0
#             if s1[i] != s2[j]:
#                 return max(f(i-1, j, s1, s2), f(i, j-1, s1, s2))
#             else:
#                 # Take
#                 take = 1 + f(i-1, j-1, s1, s2)
#                 not_take = max(f(i-1, j, s1, s2), f(i, j-1, s1, s2))
#                 return max(take, not_take)
#         m, n = len(text1), len(text2)
#         return f(m-1, n-1, text1, text2)

# # S2 - Top-down recursion with memoiation, TC = M*N, SC = M + N + MN
# class Solution:
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         def f(i, j, s1, s2, dp):
#             if i < 0 or j < 0:
#                 return 0
#             if dp[i][j] != -1:
#                 return dp[i][j]

#             if s1[i] != s2[j]:
#                 dp[i][j] = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
#             else:
#                 # Take
#                 take = 1 + f(i-1, j-1, s1, s2, dp)
#                 not_take = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
#                 dp[i][j] = max(take, not_take)
#             return dp[i][j]

#         m, n = len(text1), len(text2)
#         dp =[[-1 for _ in range(n)] for _ in range(m)]
#         return f(m-1, n-1, text1, text2, dp)

# # S3 - Top-down recursion with memoiation, updating dp index to
# # prepare bottom-up tabulation
# class Solution:
#     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
#         def f(i, j, s1, s2, dp):
#             if i == 0 or j == 0:
#                 return 0
#             if dp[i][j] != -1:
#                 return dp[i][j]

#             if s1[i-1] != s2[j-1]:
#                 dp[i][j] = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
#             else:
#                 # Take
#                 take = 1 + f(i-1, j-1, s1, s2, dp)
#                 not_take = max(f(i-1, j, s1, s2, dp), f(i, j-1, s1, s2, dp))
#                 dp[i][j] = max(take, not_take)
#             return dp[i][j]

#         m, n = len(text1), len(text2)
#         dp =[[-1 for _ in range(n+1)] for _ in range(m+1)]
#         return f(m, n, text1, text2, dp)

# # S4 - Bottom-up tabulation, TC = MN, SC = MN
# class Solution:
#     def longestCommonSubsequence(self, s1: str, s2: str) -> int:
#         m, n = len(s1), len(s2)
#         dp =[[0 for _ in range(n+1)] for _ in range(m+1)]
#         # Build base cases - no need here since we initialized dp to 0s already
#         # For nested loop from bottom
#         for i in range(1, m+1):
#             for j in range(1, n+1):
#                 if s1[i-1] != s2[j-1]:
#                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
#                 else:
#                     take = 1 + dp[i-1][j-1]
#                     not_take = max(dp[i-1][j], dp[i][j-1])
#                     dp[i][j] = max(take, not_take)

#         return dp[-1][-1]

# S5 - Bottom-up tabulation with space optimization, TC = MN, SC = N
class Solution:
def longestCommonSubsequence(self, s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
pre = [0 for _ in range(n+1)]
# Build base cases - no need here since we initialized dp to 0s already
# For nested loop from bottom
for i in range(1, m+1):
cur = [0 for _ in range(n+1)]
for j in range(1, n+1):
if s1[i-1] != s2[j-1]:
cur[j] = max(pre[j], cur[j-1])
else:
take = 1 + pre[j-1]
not_take = max(pre[j], cur[j-1])
cur[j] = max(take, not_take)
pre = cur

return pre[-1]
``````
``````def longest_common_subsequence(word1: str, word2: str) -> int:
# WRITE YOUR BRILLIANT CODE HERE
dp = [[0 for j in range(len(word2)+1)] for i in range(len(word1)+1)]
for i in range(len(word1)-1, -1, -1):
for j in range(len(word2)-1, -1, -1):
if word1[i] == word2[j]:
dp[i][j] = 1+ dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j+1])

return dp[0][0]

if __name__ == '__main__':
word1 = input()
word2 = input()
res = longest_common_subsequence(word1, word2)
print(res)

``````

nice work!

but the last solution (S5) does not optimze for space as you create “cur = [0 for _ in range(n+1)]” m times potentially using O(MN) space if the garbage collector does not kick in in the meantime

“Brute Force v2” solution is incorrect. Please check the solution.

Typo in Brute Force v2 and DFS + Memoization
The statement:
return memo[i][j] = lcs(i - 1, j - 1, word2, word2) + 1;
should be:
return memo[i][j] = lcs(i - 1, j - 1, word1, word2) + 1;

Hi, can someone explain me why some times on the illustration of some solution we start from the beginning of string for example , but in the implementation it is always from the end of the string .

``````function longestCommonSubsequence(word1, word2) {
11  let n = word1.length;
12  let m = word2.length;
13  return lcs(n, m, word1, word2);
``````

and on illustration we compare first symbols with index 0 and 0.
Thank you.

The time complexity of brute force solution seems to be incorrect.
In each recursive call, you are appending a character to the front of the string, generating a new string each time, which is clearly not an O(1) operation. I think the total complexity of the brute force should be O(n2^n + m2^m)