Complexity Analysis
def longest_common_subseq(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]What is the time and space complexity?
Work it out before scrolling down.
Time
O(m × n)
Space
O(m × n)
How to derive it
Two nested loops: outer runs m times, inner runs n times. Each cell does O(1) work → O(m × n) time. The 2D dp table has (m+1) × (n+1) entries → O(m × n) space. Since each row only depends on the previous row, this can be optimized to O(min(m, n)) space with a rolling array.