Crack the Backend

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence (LCS). A subsequence is a string generated from the original by deleting some (or no) characters without changing the relative order. The LCS does not need to be contiguous in either string.

For example, LCS of "abcde" and "ace" is "ace" (length 3). We only return the length.
Classic 2D DP: dp[i][j] = LCS of text1[0..i) and text2[0..j).

Key Observations

Define dp[i][j] = length of LCS of text1[0..i) and text2[0..j). If text1[i-1] == text2[j-1], we can match them: dp[i][j] = 1 + dp[i-1][j-1]. Otherwise we skip one character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Base: dp[0][j] = dp[i][0] = 0 (empty prefix). Fill the table row by row (or column by column). We only need the previous row to compute the current row, so space can be O(min(m,n)).

Approach

High-level: dp[i][j] = LCS length of text1[0..i) and text2[0..j). If last characters match, dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base: first row and column 0.

Steps:

m = text1.length(), n = text2.length(). prev[j] = 0 for all j (row 0). For i = 1..m: cur[0] = 0; for j = 1..n, if text1.charAt(i-1) == text2.charAt(j-1) then cur[j] = 1 + prev[j-1], else cur[j] = max(prev[j], cur[j-1]). prev = cur.
Return prev[n].

Implementation

Java

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[] prev = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        int[] cur = new int[n + 1];

        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1))
            cur[j] = 1 + prev[j - 1];
            else
            cur[j] = Math.max(prev[j], cur[j - 1]);
        }

        prev = cur;
    }

    return prev[n];
}

Test Cases

Example 1

Input

text1 = "abcde", text2 = "ace"

Expected

3

Explanation

LCS is "ace".

Complexity Analysis

Time: O(m*n).
Space: O(min(m,n)) with two rows.

Follow-ups

Print one LCS; count number of LCS.