> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/dynamic_programming/double-sequence-dp/longest-common-subsequence.md).

# Longest Common Subsequence

## Question ([LC.77](http://www.lintcode.com/en/problem/longest-common-subsequence/#))

> Given two strings, find the longest common subsequence (return length).

## Example

```
I: "ABCD", "EDCA"
O: len("A") = 1
I: "ABCD", "EACB"
O: len("AB") = 2
```

## Analysis

The classic two sequence DP. Draw a grid then tabulation.

## Approach

```
1. Define (optimal) subproblems
LCS(i,j) = longest common subsequence from A[:i] and B[:j]

2. Solve by prefix
if (A[i] == B[j])
    LCS(i,j) = LCS(i-1,i-j) + 1
else
    LCS(i,j) = Math.max(LCS(i,j-1), LCS(i-1,j))

3. Topo order
for i from 1 to n
    for j from 1 to m

4. Init base
for i from 0 to n
    LCS(i,0) = 0
for j from 0 to m
    LCS(0,j) = 0

5. Final answer
LCS(n,m)
```

## Code

```java
public int longestCommonSubsequence(String A, String B) {
    if (A == null || B == null) {
        return -1;
    }
    int n = A.length(), m = B.length();
    // create memo table
    int[][] memo = new int[n+1][m+1];
    // init base, java init 0
    // topo order
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (A.charAt(i-1) == B.charAt(j-1)) {
                memo[i][j] = memo[i-1][j-1] + 1;
            } else {
                memo[i][j] = Math.max(memo[i][j-1], memo[i-1][j]);
            }
        }
    }
    // final answer
    return memo[n][m];
}
```

## Time Complexity

`#subproblems * time/subproblem = O(m*n) * O(1) = O(mn)`