> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/longest-common-sequence-between-two-strings.md).

# Longest Common Sequence between two strings

Find the length of longest common subsequence of two given strings.

**Assumptions**

* The two given strings are not null

**Examples**

* S = “abcde”, T = “cbabdfe”, the longest common subsequence of s and t is {‘a’, ‘b’, ‘d’, ‘e’}, the length is 4.

**High Level:**

*What to memo:*

M\[i]\[j] = longest length of subsequence from first i chars of s1, first j chars of s2 

*Base case:* 

M\[0]\[j] = 0 and M\[i]\[0] = 0

*Induction rule:*

if s1\[i] == s2\[j], M\[i]\[j] = M\[i-1]\[j-1] + 1

else M\[i]\[j] = max(M\[i-1]\[j], M\[i]\[j-1]) 

```
public class Solution {
  public int longest(String source, String target) {
    //edge case
    if(source.length() == 0 || target.length() == 0) return 0;

    int[][] M = new int[source.length()][target.length()];

    // base case
    M[0][0] = source.charAt(0) == target.charAt(0) ? 1 : 0;

    for (int i = 1 ; i < source.length(); i++) {
      M[i][0] = source.charAt(i) == target.charAt(0) ? 1 : M[i-1][0];
    }

    for (int j = 1 ; j < target.length(); j++) {
      M[0][j] = source.charAt(0) == target.charAt(j) ? 1 : M[0][j-1];
    }
    
    //iterate row by row
    for(int i = 1; i < source.length();i++){ //rows
      for(int j = 1; j < target.length(); j++){ //columns
        if(source.charAt(i) == target.charAt(j)){
          M[i][j] = M[i-1][j-1] + 1;
        } else {
          M[i][j] = Math.max(M[i-1][j], M[i][j-1]);
        }
      }
    }

    return M[source.length() - 1][target.length() - 1];
  }
}
```

TC: O(N^2) 2D memo

SC: O(N^2) 2D memo

**Mistakes made:**

top row and left most column do not all equal 0. It can inherit from neighbor if matched.