# Longest Common Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-common-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/longest-common-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Accolite](https://scaleengineer.com/companies/accolite), [ByteDance](https://scaleengineer.com/companies/bytedance), [DoorDash](https://scaleengineer.com/companies/doordash), [Nutanix](https://scaleengineer.com/companies/nutanix), [tcs](https://scaleengineer.com/companies/tcs), [Optum](https://scaleengineer.com/companies/optum), [Citadel](https://scaleengineer.com/companies/citadel), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [BP](https://scaleengineer.com/companies/bp)
---
## Problem
Given two strings `text1` and `text2`, return _the length of their longest **common subsequence**._ If there is no **common subsequence**, return `0`.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

* For example, `"ace"` is a subsequence of `"abcde"`.

A **common subsequence** of two strings is a subsequence that is common to both strings.

**Example 1:**

**Input:** text1 = "abcde", text2 = "ace" 
**Output:** 3  
**Explanation:** The longest common subsequence is "ace" and its length is 3.

**Example 2:**

**Input:** text1 = "abc", text2 = "abc"
**Output:** 3
**Explanation:** The longest common subsequence is "abc" and its length is 3.

**Example 3:**

**Input:** text1 = "abc", text2 = "def"
**Output:** 0
**Explanation:** 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.

# Approaches
## Brute-Force Recursion
This approach uses a simple recursive function to explore all possible subsequences. For each pair of characters from the two strings, we make a decision: if the characters match, we include it in our common subsequence and recurse on the rest of the strings. If they don't match, we explore two possibilities: skipping the character in the first string or skipping the character in the second string, and we take the maximum length from these two branches.
**Time:** O(2^(m+n)). In the worst-case scenario (no matching characters), each function call branches into two, leading to an exponential number of calls. · **Space:** O(m + n), where m and n are the lengths of the strings. This space is used by the recursion call stack.
**Pros:** Simple to understand and implement the core logic.; Directly translates the problem's recursive definition into code.
**Cons:** Extremely inefficient due to a massive number of overlapping subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial inputs.
### Explanation
We define a recursive helper function, say `solve(i, j)`, which calculates the length of the LCS for `text1` starting from index `i` and `text2` starting from index `j`.

- **Base Case**: If either `i` or `j` reaches the end of its respective string, it means we can't find any more common characters, so we return 0.
- **Recursive Step**:
  - If `text1.charAt(i) == text2.charAt(j)`, the characters match. This character is part of a common subsequence. We add 1 to the result and recursively call the function for the next characters: `1 + solve(i + 1, j + 1)`.
  - If `text1.charAt(i) != text2.charAt(j)`, the characters do not match. We have two choices to find the longest possible subsequence:
    1. Ignore the current character of `text1` and find the LCS of `text1[i+1...]` and `text2[j...]`. This is `solve(i + 1, j)`.
    2. Ignore the current character of `text2` and find the LCS of `text1[i...]` and `text2[j+1...]`. This is `solve(i, j + 1)`.
  - We take the maximum of these two results: `Math.max(solve(i + 1, j), solve(i, j + 1))`.

The initial call to the function would be `solve(0, 0)`. This method leads to a large number of redundant calculations for the same subproblems, resulting in exponential time complexity.

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return solve(text1, text2, 0, 0);
    }

    private int solve(String text1, String text2, int i, int j) {
        // Base case: if either string is exhausted, no more common subsequence
        if (i == text1.length() || j == text2.length()) {
            return 0;
        }

        // If characters match
        if (text1.charAt(i) == text2.charAt(j)) {
            return 1 + solve(text1, text2, i + 1, j + 1);
        } else {
            // If characters don't match, explore two possibilities and take the max
            int option1 = solve(text1, text2, i + 1, j); // Skip character in text1
            int option2 = solve(text1, text2, i, j + 1); // Skip character in text2
            return Math.max(option1, option2);
        }
    }
}
```
### Algorithm
- Define a recursive function `solve(i, j)` that computes the LCS of `text1` from index `i` and `text2` from index `j`.
- **Base Case:** If `i` or `j` is out of bounds (equal to the string length), return 0.
- **Recursive Step:**
  - If `text1.charAt(i) == text2.charAt(j)`, the characters match. The result is `1 + solve(i + 1, j + 1)`.
  - If the characters do not match, we must choose the better of two options:
    1. Skip the character in `text1`: `solve(i + 1, j)`.
    2. Skip the character in `text2`: `solve(i, j + 1)`.
  - The result is `Math.max(solve(i + 1, j), solve(i, j + 1))`.
- The initial call is `solve(0, 0)`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by using a memoization table (usually a 2D array) to store the results of already computed subproblems. By caching results, we avoid redundant calculations for the same pair of indices `(i, j)`. This technique is a form of top-down dynamic programming.
**Time:** O(m * n). Each state `(i, j)` is computed only once. There are `m * n` possible states. · **Space:** O(m * n) for the memoization table, plus O(m+n) for the recursion stack. The dominant factor is the memoization table.
**Pros:** Drastically more efficient than brute-force, with polynomial time complexity.; Retains the intuitive top-down recursive structure, making it easy to reason about.
**Cons:** Requires O(m*n) space for the memoization table, which can be significant.; For very deep recursion paths (not an issue with problem constraints), it could theoretically cause a stack overflow.
### Explanation
The recursive structure is the same as the brute-force approach, but we enhance it with a cache to store intermediate results.

- We introduce a 2D array, `memo`, of size `m x n` (where `m` is `text1.length()` and `n` is `text2.length()`) to store the results of `solve(i, j)`.
- We initialize the `memo` table with a special value (e.g., -1) to indicate that a subproblem has not been solved yet.
- Inside the recursive function `solve(i, j)`, before any computation, we first check if `memo[i][j]` has already been computed. If it has, we return the stored value immediately, avoiding a costly re-computation.
- If the result is not in the memo table, we compute it using the same recursive logic as before.
- After computing the result, we store it in `memo[i][j]` before returning it.

By storing results, we ensure that each subproblem `(i, j)` is solved only once.

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] memo = new int[m][n];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return solve(text1, text2, 0, 0, memo);
    }

    private int solve(String text1, String text2, int i, int j, int[][] memo) {
        if (i == text1.length() || j == text2.length()) {
            return 0;
        }

        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        int result;
        if (text1.charAt(i) == text2.charAt(j)) {
            result = 1 + solve(text1, text2, i + 1, j + 1, memo);
        } else {
            int option1 = solve(text1, text2, i + 1, j, memo);
            int option2 = solve(text1, text2, i, j + 1, memo);
            result = Math.max(option1, option2);
        }
        
        memo[i][j] = result;
        return result;
    }
}
```
### Algorithm
- Use the same recursive structure as the brute-force approach.
- Create a 2D array `memo[m][n]` to store the results of subproblems, initialized with a value like -1.
- In the recursive function `solve(i, j)`, first check if `memo[i][j]` is already computed (i.e., not -1). If so, return the stored value.
- If not computed, calculate the result using the same recursive logic.
- Before returning the result, store it in `memo[i][j]` for future use.

## Tabulation (Bottom-Up Dynamic Programming)
This is an iterative approach to dynamic programming, also known as tabulation. Instead of a top-down recursive solution, we build the solution from the bottom up. We use a 2D DP table to store the lengths of the LCS for all prefixes of the two strings, starting from empty strings and building up to the full strings.
**Time:** O(m * n), due to the nested loops iterating through the `m x n` DP table. · **Space:** O(m * n) to store the DP table.
**Pros:** Efficient with O(m*n) time complexity.; Avoids recursion, so there is no risk of stack overflow.; Often slightly faster in practice than memoization due to lower overhead.
**Cons:** Requires O(m*n) space, which can be inefficient for very long strings.
### Explanation
We create a 2D array `dp` of size `(m+1) x (n+1)`, where `m` and `n` are the lengths of `text1` and `text2`. The cell `dp[i][j]` will store the length of the LCS of the prefix `text1[0...i-1]` and `text2[0...j-1]`.

The extra row and column handle the base cases of an empty string. `dp[0][j]` and `dp[i][0]` will be 0, which is the default initialization value for an integer array in Java.

We iterate through the strings using nested loops, with `i` from 1 to `m` and `j` from 1 to `n`. For each cell `dp[i][j]`, we apply the following logic:

- If the characters `text1.charAt(i-1)` and `text2.charAt(j-1)` are the same, it means we've found a common character. The LCS length is one more than the LCS of the strings without these characters. So, `dp[i][j] = 1 + dp[i-1][j-1]`.
- If the characters are different, we can't extend the current LCS. The LCS length will be the maximum of the LCS found by either excluding the character from `text1` (i.e., `dp[i-1][j]`) or excluding the character from `text2` (i.e., `dp[i][j-1]`). So, `dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])`.

After filling the entire table, the value at `dp[m][n]` will be the length of the LCS for the entire `text1` and `text2`.

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
```
### Algorithm
- Create a 2D DP table `dp` of size `(m+1) x (n+1)`.
- `dp[i][j]` will store the LCS length for `text1[0...i-1]` and `text2[0...j-1]`.
- The first row and column are implicitly 0, representing the LCS with an empty string.
- Iterate with `i` from 1 to `m` and `j` from 1 to `n`.
- **Fill the table:**
  - If `text1.charAt(i-1) == text2.charAt(j-1)`, then `dp[i][j] = 1 + dp[i-1][j-1]`.
  - Otherwise, `dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])`.
- The final answer is in `dp[m][n]`.

## Space-Optimized Dynamic Programming
This approach optimizes the space complexity of the bottom-up DP solution. We observe that to compute the current row `i` of the DP table, we only need information from the previous row `i-1`. This key insight allows us to discard older rows and reduce the space from O(m*n) to O(min(m,n)), making it the most memory-efficient solution.
**Time:** O(m * n). The time complexity remains the same as the standard tabulation approach. · **Space:** O(min(m, n)). We use a 1D array whose size is determined by the length of the shorter string.
**Pros:** Most efficient in terms of space complexity.; Maintains the optimal O(m*n) time complexity.; This is the preferred solution in interviews where memory constraints are a concern.
**Cons:** The logic can be slightly less intuitive, especially the single-array optimization.; Reconstructing the actual LCS string (not just its length) is more complex with this approach.
### Explanation
The time complexity of the tabulation approach is optimal, but the space can be improved. Notice that the calculation for `dp[i][j]` only depends on `dp[i-1][j-1]`, `dp[i-1][j]`, and `dp[i][j-1]`. This means we only ever need the values from the previous row and the current row.

We can use a single 1D array, `dp`, of size `n+1` (assuming `n` is the length of the shorter string). This `dp` array will represent the current row being calculated. The values it holds from the previous outer loop iteration represent the 'previous row'.

- To ensure O(min(m,n)) space, we first check which string is shorter and iterate over it in the inner loop.
- Let's assume `text2` is shorter (length `n`). We create `dp` of size `n+1`.
- We loop `i` from 1 to `m` (length of `text1`).
- Inside, we loop `j` from 1 to `n`. When we compute `dp[j]` (representing `dp[i][j]`), we need `dp[i-1][j-1]`. However, `dp[j-1]` has already been updated to be `dp[i][j-1]`. And `dp[j]` currently holds `dp[i-1][j]`. We need to save the value of `dp[i-1][j-1]` before it's overwritten. We use a variable, `prev_val`, to hold `dp[i-1][j-1]` for the current `j`.

```java
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // Ensure text2 is the shorter string to optimize space
        if (text1.length() < text2.length()) {
            String temp = text1;
            text1 = text2;
            text2 = temp;
        }
        
        int m = text1.length();
        int n = text2.length();
        
        int[] dp = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            int prev_val = 0; // This will store the value of dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // This is dp[i-1][j]
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // We need dp[i-1][j-1], which is stored in prev_val
                    dp[j] = 1 + prev_val;
                } else {
                    // We need max(dp[i-1][j], dp[i][j-1])
                    // dp[j] is currently dp[i-1][j]
                    // dp[j-1] has been updated to be dp[i][j-1]
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev_val = temp; // Update prev_val for the next j
            }
        }
        return dp[n];
    }
}
```
### Algorithm
- Observe that calculating `dp[i][j]` only requires values from the previous row (`i-1`) and the current row (`i`).
- Instead of a 2D table, use two 1D arrays, `prev` and `curr`, of size `min(m,n)+1`.
- Iterate through the longer string with the outer loop (`i`) and the shorter string with the inner loop (`j`).
- In each outer iteration, calculate the `curr` row using values from the `prev` row.
- After the inner loop, update `prev` to be `curr` for the next iteration.
- **Further Optimization:** This can be done with a single 1D array `dp` of size `min(m,n)+1`. A temporary variable is used to store the value of `dp[i-1][j-1]` before it gets overwritten.

# Solutions
### CSharp

```csharp
public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int m = text1.Length, n = text2.Length;
        int[, ] f = new int[m + 1, n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[i, j] = f[i - 1, j - 1] + 1;
                } else {
                    f[i, j] = Math.Max(f[i - 1, j], f[i, j - 1]);
                }
            }
        }
        return f[m, n];
    }
}
```

### Java

```java
class Solution {
public
  int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] f = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
          f[i][j] = f[i - 1][j - 1] + 1;
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
        }
      }
    }
    return f[m][n];
  }
}

```

### JavaScript

```javascript
/** * @param {string} text1 * @param {string} text2 * @return {number} */ var longestCommonSubsequence =
  function (text1, text2) {
    const m = text1.length;
    const n = text2.length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; ++i) {
      for (let j = 1; j <= n; ++j) {
        if (text1[i - 1] == text2[j - 1]) {
          f[i][j] = f[i - 1][j - 1] + 1;
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
        }
      }
    }
    return f[m][n];
  };

```

### CPP

```cpp
class Solution {
public:
  int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    int f[m + 1][n + 1];
    memset(f, 0, sizeof f);
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        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];
  }
};

```

### Python

```python
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]

```