Longest Common Subsequence

Background Knowledge

The Longest Common Subsequence (LCS) problem is a classic example of a dynamic programming problem. To understand this problem, you need to grasp the concept of a subsequence, which is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, given the string "ABC", some possible subsequences are "A", "B", "C", "AB", "BC", and "ABC". The LCS of two strings is the longest subsequence that is common to both strings.

In dynamic programming, we break down complex problems into smaller subproblems, solve each subproblem only once, and store the solutions to subproblems to avoid redundant computation. This approach is particularly useful for problems that have overlapping subproblems, meaning that the problem can be broken down into subproblems that may have some overlap. The LCS problem has overlapping subproblems because the LCS of two strings can be derived from the LCS of their prefixes.

To solve the LCS problem, you need to understand the concept of a 2D array or matrix, where each cell represents the LCS of two prefixes of the input strings. The value of each cell can be computed based on the values of its neighboring cells. This is a key insight in dynamic programming, where we build a solution to a complex problem by combining solutions to smaller subproblems.

Algorithm/Approach

The general approach to solve the LCS problem is to use dynamic programming with a 2D array or matrix. The algorithm pattern involves:

• Initializing a 2D array to store the lengths of LCS of prefixes of the input strings
• Filling the 2D array in a bottom-up manner, where each cell is computed based on the values of its neighboring cells
• The final solution is stored in the bottom-right cell of the 2D array

Step-by-Step Strategy

To implement the solution, follow these steps:

• Initialize a 2D array dp of size (m+1) x (n+1), where m and n are the lengths of the input strings
• Fill the first row and first column of the dp array with zeros, since the LCS of an empty string and a non-empty string is zero
• Iterate over the dp array, filling each cell dp[i][j] based on the values of its neighboring cells dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]
• If the current characters in the input strings match, the value of dp[i][j] is dp[i-1][j-1] + 1
• If the current characters do not match, the value of dp[i][j] is the maximum of dp[i-1][j] and dp[i][j-1]

Common Pitfalls

When implementing the solution, watch out for:

• Incorrect initialization of the dp array
• Incorrect computation of the values of the dp array
• Not handling the base cases correctly (e.g., when one or both of the input strings are empty)

Time & Space Complexity

The expected time complexity of the solution is $O(mn)$, where m and n are the lengths of the input strings. The expected space complexity is also $O(mn)$, since we need to store the dp array of size (m+1) x (n+1).