LCS LeetCode 1143 — 2D DP Deep Dive

LeetCode 1143 — Longest Common Subsequence — asks you to find the length of the longest subsequence that appears in both text1 and text2. A subsequence is formed by deleting some (or no) characters from a string without changing the order of the remaining characters. The subsequence does not need to occupy contiguous positions — only relative order matters.

For example, given text1 = "abcde" and text2 = "ace", the LCS is "ace" with length 3. The characters a, c, e appear in both strings in the same order, even though they are not adjacent in text1. The answer is always a non-negative integer: 0 if the strings share no characters, up to min(m, n) if one string is a subsequence of the other.

LCS is a foundational string DP problem. Unlike Longest Common Substring (which requires contiguous characters), LCS allows gaps — this makes it harder to solve greedily and naturally leads to a 2D DP table. The problem is rated Medium on LeetCode and appears frequently in interviews at top tech companies as the gateway to the string DP category.

Define dp[i][j] as the length of the longest common subsequence of text1[0..i-1] and text2[0..j-1]. The table has (m+1) rows and (n+1) columns, where m = len(text1) and n = len(text2). The extra row and column at index 0 represent the empty string — dp[0][j] = 0 and dp[i][0] = 0 for all i, j.

The recurrence has exactly two cases. If text1[i-1] == text2[j-1] (the current characters match), then dp[i][j] = dp[i-1][j-1] + 1 — we extend the LCS from the diagonal by 1. If the characters do not match, then dp[i][j] = max(dp[i-1][j], dp[i][j-1]) — we take the better result from ignoring the current character of text1 (go up) or ignoring the current character of text2 (go left). The final answer is dp[m][n].

This recurrence is clean and complete because every cell depends only on the diagonal, the cell above, and the cell to the left. There are no other cases and no tricky indices. The two-branch structure — match extends diagonal, mismatch takes max of neighbors — makes LCS the ideal problem for teaching 2D DP table construction.

Fill the table row by row from i=1 to m, and within each row from j=1 to n. The first row (i=0) and first column (j=0) are initialized to 0 because the LCS of any string with the empty string is 0. For each cell (i, j), apply the two-case recurrence: match means diagonal plus one, mismatch means max of top or left.

Walking through the example text1="abcde", text2="ace": the table is 6x4. At (1,1): a==a, dp[1][1]=dp[0][0]+1=1. At (2,1): b!=a, dp[2][1]=max(dp[1][1],dp[2][0])=max(1,0)=1. At (3,2): c==c, dp[3][2]=dp[2][1]+1=2. At (5,3): e==e, dp[5][3]=dp[4][2]+1=3. Final answer dp[5][3]=3.

The table makes the structure of the problem visible. Each diagonal step adds one matched character. The max-of-neighbors rule propagates the best LCS found so far. Reading the table is the best debugging technique — if dp[m][n] looks wrong, trace a few cells manually and compare to the expected recurrence.

The full table uses O(m*n) space. But each row only looks at the row above it — dp[i][j] depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. This means we only need to keep the previous row in memory while computing the current row. We can reduce space from O(m*n) to O(n) with a single 1D array, and further to O(min(m,n)) by always iterating over the longer string.

When updating the 1D array left to right, dp[j-1] would be overwritten before we can use it as the diagonal for dp[j]. The fix is a single prev variable: before updating dp[j], save the old dp[j] (which is dp[i-1][j-1] from the previous row) in prev, then update dp[j], then set prev = old dp[j] for the next column. This correctly reconstructs the diagonal dependency with a single extra variable.

The 1D rolling approach is a standard interview follow-up. After presenting the O(m*n) space solution, the interviewer will often ask "can you reduce memory?" Walk through the dependency analysis: current row only needs previous row, and within the row we need the diagonal which requires the prev variable trick. This demonstrates systematic space-optimization reasoning.

The dp table gives the length of the LCS but not the subsequence itself. To recover the actual string, backtrack from dp[m][n]. At each cell (i, j): if text1[i-1] == text2[j-1], the character is part of the LCS — add it to the result and move diagonally to (i-1, j-1). Otherwise, move to whichever neighbor is larger: if dp[i-1][j] >= dp[i][j-1], move up to (i-1, j); else move left to (i, j-1). Stop when i==0 or j==0.

The backtracking produces the LCS in reverse order (from the end of both strings to the beginning), so reverse the result string before returning. The time complexity of backtracking is O(m+n) because each step decrements i or j (or both), and total steps cannot exceed m+n. Space is O(m+n) for the result string.

Recovering the LCS is exactly how Unix diff and git diff work — the diff algorithm builds an LCS of lines between two files, then marks lines not in the LCS as additions or deletions. Understanding LCS backtracking is the foundation for understanding how every version control system tracks changes between files.

Python 2D version: def longestCommonSubsequence(text1, text2): m, n = len(text1), len(text2); dp = [[0]*(n+1) for _ in range(m+1)]; for i in range(1,m+1): for j in range(1,n+1): dp[i][j] = dp[i-1][j-1]+1 if text1[i-1]==text2[j-1] else max(dp[i-1][j],dp[i][j-1]); return dp[m][n]. Python 1D optimized: prev, dp = 0, [0]*(n+1); for i in range(1,m+1): prev=0; for j in range(1,n+1): temp=dp[j]; dp[j]=prev+1 if text1[i-1]==text2[j-1] else max(dp[j],dp[j-1]); prev=temp; return dp[n]. Time: O(m*n), Space: O(n).

Java 2D version: int[][] dp = new int[m+1][n+1]; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j] = text1.charAt(i-1)==text2.charAt(j-1) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j],dp[i][j-1]); return dp[m][n]. Java 1D version: int[] dp = new int[n+1]; for(int i=1;i<=m;i++){int prev=0; for(int j=1;j<=n;j++){int temp=dp[j]; dp[j]=text1.charAt(i-1)==text2.charAt(j-1)?prev+1:Math.max(dp[j],dp[j-1]); prev=temp;}} return dp[n]. Both are O(m*n) time and O(n) space.

To recover the actual LCS string, keep the full 2D table and backtrack: StringBuilder sb = new StringBuilder(); int i=m, j=n; while(i>0 && j>0){ if(text1.charAt(i-1)==text2.charAt(j-1)){sb.append(text1.charAt(i-1)); i--; j--;} else if(dp[i-1][j]>=dp[i][j-1]) i--; else j--;} return sb.reverse().toString(). Python equivalent uses a list and reversed join.

Edit Distance (LeetCode 72) is the closest relative of LCS. Instead of counting matches, edit distance counts the minimum number of insertions, deletions, and substitutions to transform one string into another. The recurrence is similar: if characters match, dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). Both LCS and edit distance fill an (m+1) x (n+1) table — understanding one makes the other immediate.

Interleaving String (LeetCode 97) asks whether s3 can be formed by interleaving characters from s1 and s2. The 2D DP table is identical in size: dp[i][j] is true if s3[0..i+j-1] can be formed from s1[0..i-1] and s2[0..j-1]. Longest Palindromic Subsequence (LeetCode 516) reduces to LCS of a string with its reverse — the longest palindromic subsequence equals the LCS of s and reversed(s).

The string DP family — LCS, Edit Distance, Interleaving String, Longest Palindromic Subsequence, Distinct Subsequences — all share the same 2D table structure where dp[i][j] encodes the answer for prefixes of two strings. Once you can set up and fill the LCS table confidently, every other string DP problem is a variation on the same template. LCS is the foundation of this entire category.