Problem Description

You are given two strings text1 and text2. Your task is to find the length of their longest common subsequence.

A subsequence is a sequence that can be derived from a string by deleting some characters (possibly none) without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde" because you can delete 'b' and 'd' while keeping the relative positions of 'a', 'c', and 'e'.

A common subsequence is a subsequence that appears in both strings. The longest common subsequence is the common subsequence with the maximum possible length.

The solution uses dynamic programming with a 2D table f[i][j] where each cell represents the length of the longest common subsequence between the first i characters of text1 and the first j characters of text2.

The algorithm works by iterating through both strings and applying these rules:

• If characters at position i-1 in text1 and position j-1 in text2 match, we extend the previous longest common subsequence by 1: f[i][j] = f[i-1][j-1] + 1
• If characters don't match, we take the maximum of either excluding the current character from text1 or excluding it from text2: f[i][j] = max(f[i-1][j], f[i][j-1])

The final answer is stored in f[m][n], where m and n are the lengths of text1 and text2 respectively.

If no common subsequence exists, the function returns 0.

Intuition

The key insight is that we can build the solution incrementally by comparing characters from both strings one by one. When we look at any position in both strings, we face a decision problem: should we include the current characters in our subsequence or not?

Think of it this way: if we already know the longest common subsequence for smaller portions of both strings, we can use that information to solve for larger portions. This naturally leads to a dynamic programming approach.

When comparing character i from text1 and character j from text2, two scenarios arise:

1. Characters match: If text1[i-1] == text2[j-1], we've found a common character! We can add this character to whatever longest common subsequence existed before these positions. The length increases by 1 from the diagonal predecessor f[i-1][j-1].

2. Characters don't match: We can't use both characters, so we need to decide which one to skip. We have two choices:

   • Skip the character from text1 and keep the one from text2: look at f[i-1][j]
   • Skip the character from text2 and keep the one from text1: look at f[i][j-1]

   Since we want the longest subsequence, we take the maximum of these two options.

The beauty of this approach is that we're breaking down a complex problem into smaller subproblems. By the time we need to compute f[i][j], we've already computed all the smaller subproblems it depends on. Starting from empty strings (base case where all values are 0), we gradually build up to the full solution.

This bottom-up construction ensures we never miss any potential common subsequence, as we systematically explore all possibilities of including or excluding characters while maintaining their relative order.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using a 2D dynamic programming table. Let's walk through the implementation step by step:

1. Initialize the DP Table:

f = [[0] * (n + 1) for _ in range(m + 1)]

We create a 2D table f with dimensions (m+1) × (n+1), where m and n are the lengths of text1 and text2 respectively. The extra row and column represent empty string scenarios (base cases), all initialized to 0.

2. Fill the DP Table: We iterate through each cell using nested loops:

for i in range(1, m + 1):
    for j in range(1, n + 1):

3. Apply the State Transition Equation: For each cell f[i][j], we apply the recurrence relation:

In code:

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

Note that we use text1[i-1] and text2[j-1] because string indices are 0-based while our DP table indices start from 1.

4. Return the Result:

return f[m][n]

The bottom-right cell f[m][n] contains the length of the longest common subsequence of the entire text1 and text2.

Time Complexity: O(m × n) - We fill each cell in the m × n table exactly once.

Space Complexity: O(m × n) - We use a 2D table to store intermediate results.

The algorithm systematically builds up the solution from smaller subproblems to larger ones, ensuring that when we compute any cell f[i][j], all the cells it depends on (f[i-1][j-1], f[i-1][j], and f[i][j-1]) have already been computed.

Example Walkthrough

Let's walk through finding the longest common subsequence of text1 = "ace" and text2 = "aec".

Step 1: Initialize the DP table

We create a 4×4 table (since both strings have length 3, we need 3+1 dimensions). The first row and column represent empty strings, initialized to 0:

    ""  a  e  c
""   0  0  0  0
a    0  
c    0  
e    0  

Step 2: Fill the table row by row

For i=1, j=1: Comparing 'a' (from "ace") with 'a' (from "aec")

• Characters match! So f[1][1] = f[0][0] + 1 = 0 + 1 = 1

For i=1, j=2: Comparing 'a' with 'e'

• Characters don't match. f[1][2] = max(f[0][2], f[1][1]) = max(0, 1) = 1

For i=1, j=3: Comparing 'a' with 'c'

• Characters don't match. f[1][3] = max(f[0][3], f[1][2]) = max(0, 1) = 1

After row 1:

    ""  a  e  c
""   0  0  0  0
a    0  1  1  1
c    0  
e    0  

For i=2, j=1: Comparing 'c' with 'a'

• Characters don't match. f[2][1] = max(f[1][1], f[2][0]) = max(1, 0) = 1

For i=2, j=2: Comparing 'c' with 'e'

• Characters don't match. f[2][2] = max(f[1][2], f[2][1]) = max(1, 1) = 1

For i=2, j=3: Comparing 'c' with 'c'

• Characters match! f[2][3] = f[1][2] + 1 = 1 + 1 = 2

After row 2:

    ""  a  e  c
""   0  0  0  0
a    0  1  1  1
c    0  1  1  2
e    0  

For i=3, j=1: Comparing 'e' with 'a'

• Characters don't match. f[3][1] = max(f[2][1], f[3][0]) = max(1, 0) = 1

For i=3, j=2: Comparing 'e' with 'e'

• Characters match! f[3][2] = f[2][1] + 1 = 1 + 1 = 2

For i=3, j=3: Comparing 'e' with 'c'

• Characters don't match. f[3][3] = max(f[2][3], f[3][2]) = max(2, 2) = 2

Final table:

    ""  a  e  c
""   0  0  0  0
a    0  1  1  1
c    0  1  1  2
e    0  1  2  2

Result: The value at f[3][3] = 2 tells us the longest common subsequence has length 2. This corresponds to the subsequence "ac" which appears in both strings (though not necessarily consecutively).

The key insight is how the table builds up: when characters match, we extend the diagonal's subsequence by 1. When they don't match, we carry forward the best result from either excluding the current character from text1 (looking up) or from text2 (looking left).

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of text1 and n is the length of text2. This is because the algorithm uses two nested loops: the outer loop iterates m times (from 1 to m+1), and the inner loop iterates n times (from 1 to n+1). Each cell in the DP table is computed exactly once with constant time operations (comparison and max calculation).

The space complexity is O(m × n). The algorithm creates a 2D DP table f with dimensions (m+1) × (n+1) to store the intermediate results for computing the longest common subsequence. Each cell stores a single integer value representing the length of the longest common subsequence up to that position in both strings.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion Between String and DP Table

The Pitfall: One of the most frequent mistakes is confusing the indices when accessing characters from the strings versus indices in the DP table. The DP table uses 1-based indexing conceptually (where dp[i][j] represents the LCS of the first i characters of text1 and first j characters of text2), while strings use 0-based indexing.

Incorrect Code Example:

# Wrong: Using same index for both string and DP table
if text1[i] == text2[j]:  # This will cause IndexError or wrong comparison
    dp[i][j] = dp[i - 1][j - 1] + 1

Correct Solution:

# Correct: Adjusting index when accessing string characters
if text1[i - 1] == text2[j - 1]:  # i-1 and j-1 for 0-based string indexing
    dp[i][j] = dp[i - 1][j - 1] + 1

2. Space Optimization Mistake

The Pitfall: When attempting to optimize space from O(m×n) to O(min(m,n)) using a 1D array, developers often forget that we need the diagonal value dp[i-1][j-1] which gets overwritten.

Incorrect Space-Optimized Attempt:

# Wrong: Lost diagonal value after updating current cell
dp = [0] * (len2 + 1)
for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if text1[i - 1] == text2[j - 1]:
            dp[j] = dp[j - 1] + 1  # dp[j-1] is already updated, not the diagonal!

Correct Space-Optimized Solution:

# Correct: Store diagonal value before updating
dp = [0] * (len2 + 1)
for i in range(1, len1 + 1):
    prev_diagonal = 0
    for j in range(1, len2 + 1):
        temp = dp[j]  # Store current value (will be diagonal for next iteration)
        if text1[i - 1] == text2[j - 1]:
            dp[j] = prev_diagonal + 1
        else:
            dp[j] = max(dp[j], dp[j - 1])
        prev_diagonal = temp  # Update diagonal for next iteration

3. Incorrect Base Case Initialization

The Pitfall: Initializing the DP table with wrong dimensions or forgetting to account for empty string cases.

Incorrect Initialization:

# Wrong: Not accounting for empty string cases
dp = [[0] * len2 for _ in range(len1)]  # Missing the +1 for both dimensions

Correct Solution:

# Correct: Include space for empty string representation
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

4. Returning Wrong Cell Value

The Pitfall: After filling the DP table, returning the wrong cell value or using incorrect indices for the final answer.

Incorrect Return:

# Wrong: Using wrong indices
return dp[len1 - 1][len2 - 1]  # This is not the bottom-right cell

Correct Solution:

# Correct: Return the actual bottom-right cell
return dp[len1][len2]

These pitfalls often lead to incorrect results, runtime errors, or subtle bugs that are hard to debug. Always remember that the DP table has one extra row and column compared to the string lengths, and be careful with index mapping between the conceptual problem space and the actual implementation.