Return the length of the longest common subsequence (LCS) of two strings — the longest sequence of characters appearing in both, in the same order (not necessarily contiguous). "LCS" is a classic DP pattern you'll see again.
overlapSubsequence(a, b)
Input format: a | b.
a="abcdef", b="aXbXcXf" // → 4 ("abcf")
a="abc", b="def" // → 0
a="aa", b="aaaa" // → 2
Walk both strings with two pointers, starting at the front. If the characters match, that character joins the common subsequence — count it, advance both pointers. If they don't match, give up on one: skip the current character of the first string, or skip the current character of the second. Since you don't know which is better, try both and take the longer result.
Once either pointer passes the end of its string, nothing's left to match — 0.
Different skip sequences frequently land on the same (i, j) pair later — skipping in A then B can reach the same pair as skipping in B then A. The naive recursion recomputes the best result from that pair every time, even though it never depends on the specific history. This compounds exponentially as the strings grow.
The best result from here depends only on the current (i, j) pair, not the path of matches and skips that got there. Cache keyed by (i, j). Check before recursing; otherwise apply match/skip logic, store, return.
At most (n+1) × (m+1) distinct pairs for strings of length n, m — O(n·m) instead of exponential. "Two pointers into two sequences, branch on match vs. skip, cache by the pair" is the foundation for edit distance, string interleaving, and sequence alignment.
def overlap_subsequence(a, b):
memo = {}
def lcs(i, j):
if i >= len(a) or j >= len(b):
return 0
key = (i, j)
if key in memo:
return memo[key]
if a[i] == b[j]:
res = 1 + lcs(i + 1, j + 1)
else:
res = max(lcs(i + 1, j), lcs(i, j + 1))
memo[key] = res
return res
return lcs(0, 0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.