Longest Common Subsequence

NeetCode: Longest Common Subsequence · LeetCode: 1143. Longest Common Subsequence · Difficulty: Medium

Given two strings text1 and text2 (Java Strings), return the length of their longest common subsequence. A subsequence keeps the relative order of characters but may skip some. Return 0 if there is none.

Example

Text

Input:  text1 = "abcde", text2 = "ace"    Output: 3   ("ace")
Input:  text1 = "abc",   text2 = "def"    Output: 0

Brute force: plain recursion

Compare the first characters of the two remaining suffixes. If they are equal, they can both be part of the answer, so take 1 + lcs(rest, rest). If they differ, at least one of them is not used, so try dropping each and keep the better result. Without remembering answers the two-way branch on mismatches re-solves the same pair of suffixes many times.

Java

class Solution {
    private int lcs(String a, String b, int i, int j) {
        if (i == a.length() || j == b.length()) {
            return 0;
        }
        if (a.charAt(i) == b.charAt(j)) {
            return 1 + lcs(a, b, i + 1, j + 1);
        }
        return Math.max(lcs(a, b, i + 1, j), lcs(a, b, i, j + 1));
    }

    public int longestCommonSubsequence(String text1, String text2) {
        return lcs(text1, text2, 0, 0);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
        System.out.println(sol.longestCommonSubsequence("abc", "def"));
        System.out.println(sol.longestCommonSubsequence("", "abc"));
        System.out.println(sol.longestCommonSubsequence("abc", "abc"));
    }
}

Output

Time: O(2^(m+n)). Space: O(m + n).

Better: 2D table

The state is the pair (i, j), so there are (m + 1) * (n + 1) subproblems. Let dp[i][j] be the LCS length of the first i characters of text1 and the first j of text2. The extra row and column of zeros represent the empty prefix. Equal last characters extend the diagonal (dp[i-1][j-1] + 1); otherwise take the better of dropping a character from either string.

Java

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];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
        System.out.println(sol.longestCommonSubsequence("abc", "def"));
        System.out.println(sol.longestCommonSubsequence("", "abc"));
        System.out.println(sol.longestCommonSubsequence("abc", "abc"));
    }
}

Output

Time: O(m · n). Space: O(m · n).

Optimal: two rolling rows

Row i only reads row i - 1, so keep two int[] rows and swap the references (no copying). Make the shorter string the column dimension to keep the rows small. The running time is unchanged; only the memory shrinks.

Java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        String a = text1, b = text2;
        if (b.length() > a.length()) {
            String t = a; // swap so that b is the shorter string
            a = b;
            b = t;
        }
        int[] prev = new int[b.length() + 1];
        int[] cur = new int[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    cur[j] = prev[j - 1] + 1;
                } else {
                    cur[j] = Math.max(prev[j], cur[j - 1]);
                }
            }
            int[] t = prev; // swap the two row references
            prev = cur;
            cur = t;
        }
        return prev[b.length()];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
        System.out.println(sol.longestCommonSubsequence("abc", "def"));
        System.out.println(sol.longestCommonSubsequence("", "abc"));
        System.out.println(sol.longestCommonSubsequence("abc", "abc"));
    }
}

Output

Time: O(m · n). Space: O(min(m, n)).

Column 0 of both rows always stays 0, which is the empty-prefix base case, so swapping the rows never leaves stale data behind. Recovering the subsequence itself (not only its length) needs the full table.