Difficulty: Medium · LeetCode 1143

Problem

Given two strings text1 and text2, return length of their longest common subsequence.

Understanding the problem

At each pair of characters: if equal → take both (1 + dfs(i+1, j+1)). Otherwise → skip one side (max(dfs(i+1, j), dfs(i, j+1))).

Intuition

2D DP matrix dp[i][j] where i and j index text1 and text2. Space can be optimized to 1D row array.

Approach

Create dp grid of size (m+1) x (n+1).
Loop i from 1 to m and j from 1 to n.
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].

Naive Solution — Recursion

Recursively match characters or branch by skipping one side.

Python

class Solution:
    def longestCommonSubsequence(self, text1, text2):

        def dfs(i, j):
            if i == len(text1) or j == len(text2):
                return 0

            if text1[i] == text2[j]:
                return 1 + dfs(i + 1, j + 1)

            return max(
                dfs(i + 1, j),
                dfs(i, j + 1)
            )

        return dfs(0, 0)

C++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        return dfs(text1, text2, 0, 0);
    }

private:
    int dfs(const string& text1, const string& text2, int i, int j) {
        if (i == (int)text1.size() || j == (int)text2.size()) return 0;

        if (text1[i] == text2[j]) {
            return 1 + dfs(text1, text2, i + 1, j + 1);
        }

        return max(dfs(text1, text2, i + 1, j), dfs(text1, text2, i, j + 1));
    }
};

Java

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

    private int dfs(String text1, String text2, int i, int j) {
        if (i == text1.length() || j == text2.length()) return 0;

        if (text1.charAt(i) == text2.charAt(j)) {
            return 1 + dfs(text1, text2, i + 1, j + 1);
        }

        return Math.max(dfs(text1, text2, i + 1, j), dfs(text1, text2, i, j + 1));
    }
}

JavaScript

var longestCommonSubsequence = function(text1, text2) {
    const dfs = (i, j) => {
        if (i === text1.length || j === text2.length) return 0;

        if (text1[i] === text2[j]) {
            return 1 + dfs(i + 1, j + 1);
        }

        return Math.max(dfs(i + 1, j), dfs(i, j + 1));
    };

    return dfs(0, 0);
};

Time: O(2^(m+n)) · Aux Space: O(m+n)

Optimized Code (Python 3)

Python

class Solution:
    def longestCommonSubsequence(self, text1, text2):

        m = len(text1)
        n = 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]

C++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int 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

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] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}

JavaScript

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length;
    const n = text2.length;

    const dp = Array.from({ length: m + 1 }, () => new 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]) {
                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];
};

Time: O(mn) · Space: O(min(m,n)) (Space Optimized) / O(mn) (2D DP Matrix)

Takeaway

Two-String DP — Compare prefix i of string A and prefix j of string B.