Hints — p59 Longest Common Subsequence

Hint 1. Subsequence (not substring). Think recursion on prefix lengths: f(i, j) = LCS of text1[:i] and text2[:j].

Hint 2. Two cases. If text1[i-1] == text2[j-1]: this character must (WLOG) be in the LCS, so f(i, j) = f(i-1, j-1) + 1. Else: drop one side, f(i, j) = max(f(i-1, j), f(i, j-1)).

Hint 3. Memoize → equivalent to a 2D dp[i][j] table, bottom-up. O(m·n) time and space. Base: dp[0][j] = dp[i][0] = 0.

Hint 4. Space compress to O(min(m, n)) by keeping just one row. Trick: when overwriting dp[j], save its old value first because the match case needs the diagonal dp[i-1][j-1].

Hint 5. To reconstruct the actual LCS string (not just length), keep the full 2D table and walk back from dp[m][n]: on match, prepend the character and step diagonally; on mismatch, step toward the larger of dp[i-1][j] and dp[i][j-1].

If stuck: see solution.py.