Longest Common Subsequence

Problem

Given two strings text1 and text2, return the length of the longest common subsequence between the two strings if one exists, otherwise return 0.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

• For example, "cat" is a subsequence of "crabt".

A common subsequence of two strings is a subsequence that exists in both strings.

Examples

Example 1:

Input: text1 = "cat", text2 = "crabt" 

Output: 3 

Explanation: The longest common subsequence is “cat” which has a length of 3.

Example 2:

Input: text1 = "abcd", text2 = "abcd"

Output: 4

Example 3:

Input: text1 = "abcd", text2 = "efgh"

Output: 0

Constraints

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

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string text1 and n is the length of the string text2.

Solution

DFS returns the length of the LCS between the suffixes text1[i:] and text2[j:]. We use the suffix-based DFS invariant because it turns each state into a small local decision, match both characters or skip one side, avoiding the expensive inner loop over all future matching index pairs.

class Solution {
public:
    int longestCommonSubsequence(const string &text1, const string &text2) {
        const auto N = text1.size();
        const auto M = text2.size();
        std::vector<int> memo(N * M, -1);
 
        // dfs(i, j) returns the length of the LCS between the suffixes
        // text1[i:] and text2[j:].
        //
        // At each state, we decide what to do with text1[i] and text2[j]:
        // - If they match, include that character and advance both indices.
        // - Otherwise, skip one character from either text1 or text2.
        std::function<int(int, int)> dfs;
        dfs = [&](int i, int j) -> int {
            // Out of bounds
            if (i >= N || j >= M) { return 0; }
            auto idx = i * M + j;
            // Known result
            if (memo[idx] != -1) { return memo[idx]; }
 
            int result = 0;
            if (text1[i] == text2[j]) {
                result = 1 + dfs(i + 1, j + 1);
            } else {
                result = std::max(dfs(i + 1, j), dfs(i, j + 1));
            }
            memo[idx] = result;
            return result;
        };
        return dfs(0, 0);
    }
};