Longest Common Subsequence

medium
Dynamic ProgrammingStringDynamic Programming

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence that can be derived from a string by deleting some or no characters without changing the relative order of the remaining characters. If there is no common subsequence, return 0.

Examples

Example 1

  • Input: text1 = "abcde", text2 = "ace"
  • Output: 3
  • Explanation: The longest common subsequence is "ace" with length 3.

Example 2

  • Input: text1 = "abc", text2 = "abc"
  • Output: 3
  • Explanation: The entire string "abc" is the longest common subsequence.

Example 3

  • Input: text1 = "abc", text2 = "def"
  • Output: 0
  • Explanation: The two strings share no common characters.

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English characters.

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

Compare characters from both strings starting at the end. If the characters match, they are part of the LCS and we recurse on both strings with one less character. If they do not match, we try two options: skip the last character of text1 or skip the last character of text2, and take the maximum. This explores all possible subsequence pairings but has exponential overlap.

Algorithm

  1. If either string is empty, return `0`.
  2. If the last characters match, return `1 + recurse(text1[:-1], text2[:-1])`.
  3. Otherwise, return `max(recurse(text1[:-1], text2), recurse(text1, text2[:-1]))`.
TimeO(2^(m+n)) where m and n are the lengths of the two stringsSpaceO(m + n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        return helper(text1, text2, text1.size() - 1, text2.size() - 1);
    }

    int helper(string& s1, string& s2, int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (s1[i] == s2[j]) {
            return 1 + helper(s1, s2, i - 1, j - 1);
        }
        return max(helper(s1, s2, i - 1, j), helper(s1, s2, i, j - 1));
    }
};
Java 21
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return helper(text1, text2, text1.length() - 1, text2.length() - 1);
    }

    private int helper(String s1, String s2, int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (s1.charAt(i) == s2.charAt(j)) {
            return 1 + helper(s1, s2, i - 1, j - 1);
        }
        return Math.max(helper(s1, s2, i - 1, j), helper(s1, s2, i, j - 1));
    }
}
Python 3.12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        def helper(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            if text1[i] == text2[j]:
                return 1 + helper(i - 1, j - 1)
            return max(helper(i - 1, j), helper(i, j - 1))

        return helper(len(text1) - 1, len(text2) - 1)
Go 1.26
func longestCommonSubsequence(text1 string, text2 string) int {
    var helper func(i, j int) int
    helper = func(i, j int) int {
        if i < 0 || j < 0 {
            return 0
        }
        if text1[i] == text2[j] {
            return 1 + helper(i-1, j-1)
        }
        a := helper(i-1, j)
        b := helper(i, j-1)
        if a > b {
            return a
        }
        return b
    }
    return helper(len(text1)-1, len(text2)-1)
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Build a 2D table where dp[i][j] represents the length of the LCS of text1[:i] and text2[:j]. If characters match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This eliminates redundant computation by filling the table row by row.

Algorithm

  1. Create a 2D array `dp` of size `(m+1) x (n+1)` initialized to `0`.
  2. For each `i` from 1 to `m` and `j` from 1 to `n`:
  3. Return `dp[m][n]`.
TimeO(m * n)SpaceO(m * n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};
Java 21
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), 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] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
Python 3.12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[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]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]
Go 1.26
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = dp[i-1][j]
                if dp[i][j-1] > dp[i][j] {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    return dp[m][n]
}
Approach 3

Space-Optimized DP

Intuition

Since each row of the DP table only depends on the current and previous rows, we can reduce space from O(m * n) to O(n) by keeping only two rows at a time. We alternate between a previous row and a current row, updating values as we iterate.

Algorithm

  1. Create two arrays `prev` and `curr` of size `n + 1`, initialized to `0`.
  2. For each character in `text1`, iterate through `text2`:
  3. After processing each row, swap `prev` and `curr`.
  4. Return `prev[n]`.
TimeO(m * n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<int> prev(n + 1, 0), curr(n + 1, 0);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = max(prev[j], curr[j - 1]);
                }
            }
            swap(prev, curr);
            fill(curr.begin(), curr.end(), 0);
        }
        return prev[n];
    }
};
Java 21
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[] prev = new int[n + 1];
        int[] curr = new int[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)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            int[] temp = prev;
            prev = curr;
            curr = temp;
            Arrays.fill(curr, 0);
        }
        return prev[n];
    }
}
Python 3.12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        prev = [0] * (n + 1)
        curr = [0] * (n + 1)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    curr[j] = prev[j - 1] + 1
                else:
                    curr[j] = max(prev[j], curr[j - 1])
            prev, curr = curr, [0] * (n + 1)
        return prev[n]
Go 1.26
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    prev := make([]int, n+1)
    curr := make([]int, n+1)
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                curr[j] = prev[j-1] + 1
            } else {
                curr[j] = prev[j]
                if curr[j-1] > curr[j] {
                    curr[j] = curr[j-1]
                }
            }
        }
        prev, curr = curr, make([]int, n+1)
    }
    return prev[n]
}

Frequently asked questions

What is the optimal time complexity of Longest Common Subsequence?

The most efficient approach in this guide ("Space-Optimized DP") runs in O(m * n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Longest Common Subsequence use?

Longest Common Subsequence is a medium-level Dynamic Programming problem involving String, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Longest Common Subsequence be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(m + n) for the recursion stack, while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
text1=
"abcde"
text2=
"ace"
Expected Output
3