#1143

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Common Subsequence

Find the length of the longest common subsequence between two strings using state transition dynamic programming for efficiency.

string dynamic programming

Problem Statement

Given two strings text1 and text2, determine the length of their longest common subsequence. A subsequence can be formed by deleting zero or more characters without changing the order of remaining characters. If no common subsequence exists, return 0.

A common subsequence is a sequence that appears in both strings in the same relative order. Your task is to compute the maximum length of such a sequence, considering all possible subsequences, and design an algorithm that scales efficiently with string lengths up to 1000 characters.

Examples

Example 1

Input: text1 = "abcde", text2 = "ace"

Output: 3

The longest common subsequence is "ace" and its length is 3.

Example 2

Input: text1 = "abc", text2 = "abc"

Output: 3

The longest common subsequence is "abc" and its length is 3.

Example 3

Input: text1 = "abc", text2 = "def"

Output: 0

There is no such common subsequence, so the result is 0.

Constraints

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

Solution Approach

Dynamic Programming Table Setup

Create a 2D DP table where DP[i][j] represents the length of the longest common subsequence between text1[0..i-1] and text2[0..j-1]. Initialize the first row and column to zeros to represent empty string prefixes.

State Transition Update

Iterate through both strings. If text1[i-1] equals text2[j-1], set DP[i][j] = DP[i-1][j-1] + 1. Otherwise, set DP[i][j] = max(DP[i-1][j], DP[i][j-1]). This captures the inclusion or exclusion of current characters, reflecting the state transition dynamic programming pattern.

Result Extraction and Optimization

After filling the DP table, DP[m][n] holds the LCS length for the full strings. For space optimization, you can reduce the table to two rows, updating iteratively, which preserves correctness while lowering memory usage from O(m*n) to O(n).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) because each DP cell is computed once, where m and n are the lengths of text1 and text2. Space complexity is O(m n) for the full table, but can be reduced to O(n) using two-row optimization.

What Interviewers Usually Probe

The candidate recognizes DP[i][j] as the key state representation for subsequence lengths.
They correctly identify state transitions for character matches versus mismatches.
They optimize space with rolling rows to reduce memory without affecting correctness.

Common Pitfalls or Variants

Common pitfalls

Confusing subsequence with substring, leading to incorrect DP updates.
Forgetting to initialize DP table edges, causing index errors or wrong LCS length.
Using recursive solutions without memoization, leading to exponential time complexity.

Follow-up variants

Return the actual longest common subsequence string instead of just its length.
Compute LCS for more than two strings using multidimensional DP.
Apply the pattern to sequences of numbers or other comparable items instead of characters.

FAQ

What is the best approach for solving Longest Common Subsequence?

State transition dynamic programming is optimal, using a DP table where DP[i][j] tracks the LCS length of prefixes of both strings.

Can LCS be solved recursively without DP?

Yes, but naive recursion has exponential time complexity; memoization or DP is needed for strings up to length 1000.

How do I optimize space in LCS DP solutions?

You can keep only two rows of the DP table at a time, updating iteratively to reduce space from O(m*n) to O(n).

Does LCS require contiguous characters?

No, LCS allows characters to be non-contiguous while maintaining relative order, which differentiates it from substring problems.

What common mistakes occur in LCS problems?

Confusing subsequences with substrings, missing base cases, and attempting recursion without memoization are frequent errors.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the length of the longest common subsequence of the first $i$ characters of $text1$ and the first $j$ characters of $text2$. Therefore, the answer is $f[m][n]$, where $m$ and $n$ are the lengths of $text1$ and $text2$, respectively.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    f[i][j] = f[i - 1][j - 1] + 1
                else:
                    f[i][j] = max(f[i - 1][j], f[i][j - 1])
        return f[m][n]

Continue Practicing

#1147 longest chunked palindrome decomposition #1092 shortest common supersequence #1048 longest string chain