Longest Common Subsequence LeetCode Solution Explained

If there is one problem that makes two-dimensional dynamic programming on strings finally make sense, it is LeetCode 1143 — Longest Common Subsequence. The problem is clean, the recurrence is elegant, and once you see how the table fills, every other string DP problem becomes a variation on the same theme.

The longest common subsequence leetcode problem asks you to find the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. It is the foundation behind diff tools, DNA sequence alignment, and several harder interview problems like Edit Distance and Shortest Common Supersequence.

In this walkthrough, you will build the recurrence from scratch, fill the 2D table step by step, and then compress it down to a single row. By the end, LCS will feel less like a memorized trick and more like a framework you can adapt on the fly.

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. For example, "ace" is a subsequence of "abcde" but "aec" is not.

The key distinction is between a subsequence and a substring. A substring must be contiguous — characters side by side in the original string. A subsequence only needs to preserve relative order. This difference is exactly what makes LCS a 2D DP problem instead of a simpler sliding window or two-pointer problem.

Consider text1 = "abcde" and text2 = "ace". The longest common subsequence is "ace" with length 3. Both strings contain a, c, and e in that order, even though other characters appear between them in text1.

The brute-force approach would enumerate all subsequences of one string and check each against the other. Since a string of length n has 2^n subsequences, this is exponentially slow. Dynamic programming collapses the overlapping subproblems and solves the whole thing in O(m * n) time.

The LCS dynamic programming recurrence compares characters one pair at a time. Define dp[i][j] as the length of the longest common subsequence of text1[0..i-1] and text2[0..j-1]. At every cell, you face exactly two scenarios.

If text1[i-1] equals text2[j-1], both characters match and must be part of the LCS. You take the answer from dp[i-1][j-1] and add one. This diagonal move is the core of every 2D string DP problem — a match always comes from the top-left neighbor.

If the characters do not match, you skip one character from either string and take whichever gives the longer subsequence: max(dp[i-1][j], dp[i][j-1]). Skipping from the top means you ignore the current character of text1. Skipping from the left means you ignore the current character of text2.

This two-branch recurrence is what makes LCS the template for 2D string DP. Edit Distance adds a substitution cost. Shortest Common Supersequence adds characters instead of skipping them. But the skeleton — match diagonally, skip horizontally or vertically — stays the same.

Start by creating a table with (m+1) rows and (n+1) columns, where m and n are the lengths of text1 and text2. The extra row and column represent the empty-string base cases — comparing anything against an empty string yields an LCS of length zero.

Fill the table row by row, left to right. For each cell dp[i][j], check whether text1[i-1] equals text2[j-1]. If they match, write dp[i-1][j-1] + 1. Otherwise, write max(dp[i-1][j], dp[i][j-1]). The final answer lives in dp[m][n], the bottom-right corner of the table.

Walk through the example text1 = "abcde", text2 = "ace". The first row and first column are all zeros. When you reach i=1 (a) and j=1 (a), the characters match, so dp[1][1] = dp[0][0] + 1 = 1. Moving across, a does not equal c or e, so those cells inherit from the left or above. The pattern repeats: matches create diagonal jumps, mismatches propagate the running maximum.

The time complexity is O(m * n) since you fill every cell exactly once. The space complexity is also O(m * n) for the full table. Both are optimal for the general case — you cannot do better than examining every character pair.

The full 2D table uses O(m * n) memory, but look at the recurrence again. Each cell depends only on the current row and the previous row. That means you can compress the table to just two rows of length n+1 and alternate between them. This drops memory from O(m * n) to O(n).

You can go further. If you process the row left to right, dp[j-1] has already been updated to the current row value, but you need the previous row value of dp[j-1] for the diagonal. The trick is to save dp[j-1] in a temporary variable before overwriting it. With this single-row approach, space drops to O(min(m, n)) if you iterate over the shorter string in the inner loop.

Here is the LCS bottom up approach with space optimization. Use a single array prev of length n+1 initialized to zeros. For each character in text1, create or reuse a curr array. Walk through text2, applying the same recurrence but reading from prev for the row above and using a saved diagonal value for matches.

This LCS space optimization is the standard technique for any 2D DP where you only look one row back. It applies directly to Edit Distance, Minimum Path Sum, and many grid DP problems. Master it here and you will reuse it everywhere.

Empty string inputs are the simplest edge case. If either text1 or text2 is empty, the LCS is zero. The base-case row and column of zeros handle this automatically, so no special-case code is needed.

When both strings are identical, every character matches in order and the LCS equals the full string length. The diagonal of the table fills with 1, 2, 3, ... up to n. When the strings share no common characters at all, every cell propagates zeros and the answer is zero.

Single-character strings, strings of length one versus a long string, and strings with repeated characters are all worth testing. Repeated characters can create multiple valid LCS paths — the length is unique, but the actual subsequence is not. The problem only asks for length, so this does not affect correctness.

LCS is closely related to several other leetcode 1143 solution family problems. Edit Distance (LeetCode 72) adds insertion, deletion, and substitution costs. Shortest Common Supersequence (LeetCode 1092) builds the shortest string containing both inputs as subsequences — its length equals m + n minus the LCS length. Longest Increasing Subsequence (LeetCode 300) is the 1D cousin that uses a patience-sorting approach instead of a 2D table.

LCS is the blueprint for the entire family of 2D string DP problems. The match-or-skip recurrence, the extra base-case row and column, the row-by-row fill order, and the space optimization trick — these are not LCS-specific. They are the framework you will reuse for Edit Distance, regular expression matching, interleaving strings, and dozens of other problems.

Once you internalize this 2D dp string framework, new problems become a matter of adjusting the recurrence rather than inventing a solution from scratch. What changes between problems is what happens on a match, what happens on a mismatch, and what the base cases represent. The structure stays constant.

If you want to drill LCS and similar patterns until they are automatic, YeetCode flashcards let you review the recurrence, base cases, and optimization tricks with spaced repetition. Recognizing the pattern is the bottleneck in interviews — the code follows once you see it. Build that pattern recognition and 2D string DP will never feel intimidating again.