Longest Common Subsequence

Flatten Binary Tree to Linked List

Generate Parentheses

Find the length of the longest subsequence shared by two strings while preserving character order.

Given two strings `text1` and `text2`, return the length of their **longest common subsequence**. A subsequence keeps the original left-to-right order of characters, but the chosen characters do not need to be adjacent.

**Input / output**
- Input: `text1: str`, `text2: str`
- Output: `int` — the length of the longest subsequence common to both strings

**Examples**
1. `text1 = "abcde"`, `text2 = "ace"` returns `3` because `"ace"` is a common subsequence.
2. `text1 = "abc"`, `text2 = "abc"` returns `3` because the entire string matches.
3. `text1 = "abc"`, `text2 = "def"` returns `0` because they share no characters in order.

**Constraints**
- `0 <= text1.length, text2.length <= 1000`
- `text1` and `text2` contain only lowercase English letters

**Follow-up**
How would you reconstruct one actual longest common subsequence string, not just its length? Can you reduce the dynamic-programming table from `O(m * n)` space to `O(min(m, n))` space?

- 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.

Understand subsequences and why brute force fails

- 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.

Start from the naive recursion

- 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.

Cache overlapping states with memoization

- 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]`.

Build the bottom-up 2D DP table

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.

| `dp[i][j]` | "" | a | c | e |
|---|---:|---:|---:|---:|
| "" | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| ab | 0 | 1 | 1 | 1 |
| abc | 0 | 1 | 2 | 2 |
| abcd | 0 | 1 | 2 | 2 |
| abcde | 0 | 1 | 2 | 3 |

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

Dry run on `text1 = "abcde"`, `text2 = "ace"`

- 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])`.

Common mistakes

- 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.

Edge cases to test mentally

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.