Longest Common Subsequence – Solution & Complexity

• A subsequence preserves relative order, but it can skip characters, so "ace" is a subsequence of "abcde" while "aec" is not.
• A brute-force idea is to generate every subsequence of one string and check whether it appears in the other. That quickly explodes to 2^m or 2^n possibilities.
• We need a way to reuse overlapping work across prefixes of both strings, which leads naturally to dynamic programming.

• Let dfs(i, j) mean the LCS length using text1[i:] and text2[j:].
• If the current characters match, they can contribute 1 plus the best answer for the remaining suffixes.
• Otherwise, we must try skipping one character from either string and keep the better result. This is correct, but without caching it revisits the same (i, j) states many times.

• The recursive version recomputes the same suffix pairs like (i, j) again and again.
• Memoization stores each solved state once, turning the exponential tree of calls into at most m * n distinct subproblems.
• This top-down approach already reaches optimal time, but an iterative bottom-up table is often simpler to reason about and easier to visualize in interviews.

• Let dp[i][j] be the LCS length of the prefixes text1[:i] and text2[:j].
• If text1[i - 1] == text2[j - 1], then those matching characters extend the best answer for the smaller prefixes: dp[i][j] = dp[i - 1][j - 1] + 1.
• Otherwise, the best subsequence must skip one side's current character, so dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
• Filling the table row by row gives the final answer at dp[m][n].

We build a (m + 1) x (n + 1) table where rows are prefixes of text1 and columns are prefixes of text2. The first row and first column stay 0 because an empty string has LCS length 0 with anything.

The last cell is 3, so the longest common subsequence length is 3.

• Mixing up subsequences and substrings: subsequences can skip characters, substrings must stay contiguous.
• Using text1[i] and text2[j] while filling dp[i][j] for prefixes. In the table, the current characters are text1[i - 1] and text2[j - 1].
• Forgetting the extra zero-padded row and column, which causes off-by-one errors in the recurrence.
• On a mismatch, taking dp[i - 1][j - 1] directly instead of max(dp[i - 1][j], dp[i][j - 1]).

• If either string is empty, the answer is 0.
• If the strings share no characters in order, the answer stays 0 across the table.
• If the strings are identical, the answer is the full string length.
• Repeated characters still need order-aware matching, so you cannot greedily pair the first equal letter you see without considering future matches.

Use bottom-up DP over all prefix pairs. This solves m * n subproblems, each in O(1) time, so the total time is O(m*n). The full table uses O(m*n) space, and a rolling-row optimization can reduce that to O(min(m, n)) when you only need the length.