Longest Common Subsequence DP DSA Solution

Learning Outcome

After this lesson, you should be able to define a DP state over two prefixes and reduce memory to two rows.

Problem Statement

Given two strings, return the length of their longest common subsequence.

Input	Output	Why
`text1 = "abcde", text2 = "ace"`	`3`	The common subsequence "ace" has length 3.

Brute Force Approach

Generate every subsequence of both strings and compare them. This is exponential.

Optimized Approach

Use DP over prefixes. If characters match, extend the diagonal state; otherwise take the best from skipping one character.

Exact Pseudocode

prev = array of zeros with length n + 1
for i from 1 to length(text1):
  curr = array of zeros
  for j from 1 to length(text2):
    if text1[i - 1] == text2[j - 1]:
      curr[j] = prev[j - 1] + 1
    else:
      curr[j] = max(prev[j], curr[j - 1])
  prev = curr
return prev[n]

Reference Code

class Solution:
    def longestCommonSubsequence(self, text1, text2):
        n = len(text2)
        prev = [0] * (n + 1)

        for a in text1:
            curr = [0] * (n + 1)
            for j, b in enumerate(text2, 1):
                if a == b:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev = curr

        return prev[n]

Sample Dry Run

Step	State	Result
a vs ace	match a	best length becomes 1
b row	no useful match	best stays 1
c row	match c after a	best becomes 2
e row	match e after ac	answer = 3

Complexity

Measure	Value	Reason
Time	O(m * n)	Every pair of prefix positions is evaluated once.
Space	O(n)	Two rows store the previous and current prefix states.

Edge Cases

If either string is empty, the answer is 0.
Subsequence does not require contiguous characters.
Do not confuse this with longest common substring.

Interview Checklist

Use diagonal + 1 when characters match.
Use max of top and left when they do not match.
Keep row order consistent when optimizing space.

FAQs

Why does matching use the diagonal?

A match extends the best answer from both prefixes before these two characters.

Why not use one string only?

The state depends on positions in both strings, so two dimensions are needed conceptually.

What is the core pattern?

Two-string prefix DP.

Longest Common Subsequence: 2D DP Pattern