Longest Common Subsequence

Longest Common Subsequence (LCS)

LCS is the foundational 2D DP problem. It appears directly in interviews and as a subroutine in edit distance, diff tools, and DNA sequence analysis.

LCS Definition

Given strings s and t, find the length of the longest subsequence common to both. A subsequence maintains relative order but doesn't need to be contiguous.

s = "ABCBDAB"
t = "BDCAB"
LCS = "BCAB" or "BDAB" → length 4

DP Solution

public int longestCommonSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m+1][n+1];
    // dp[i][j] = LCS length of s[0..i-1] and t[0..j-1]

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;      // match: extend LCS
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // no match: take best
            }
        }
    }
    return dp[m][n];
}

Time: O(m×n), Space: O(m×n), optimizable to O(min(m,n)).

Edit Distance (Levenshtein)

public int minDistance(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m+1][n+1];

    for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all of s
    for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all of t

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];               // no operation needed
            } else {
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],  // replace
                                Math.min(dp[i-1][j],    // delete from s
                                         dp[i][j-1]));  // insert into s
            }
        }
    }
    return dp[m][n];
}

Longest Common Substring (contiguous)

public int longestCommonSubstring(String s, String t) {
    int m = s.length(), n = t.length(), max = 0;
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1; // must be contiguous
                max = Math.max(max, dp[i][j]);
            }
            // else dp[i][j] = 0 (restart — subsequence breaks here)
        }
    }
    return max;
}

Shortest Common Supersequence

SCS = both strings as subsequences. Length = m + n - LCS(s,t).

public int shortestCommonSupersequence(String s, String t) {
    return s.length() + t.length() - longestCommonSubsequence(s, t);
}

Longest Palindromic Subsequence

// LPS of s = LCS(s, reverse(s))
public int longestPalindromicSubsequence(String s) {
    return longestCommonSubsequence(s, new StringBuilder(s).reverse().toString());
}

Reconstructing the LCS

public String reconstructLCS(String s, String t, int[][] dp) {
    StringBuilder sb = new StringBuilder();
    int i = s.length(), j = t.length();
    while (i > 0 && j > 0) {
        if (s.charAt(i-1) == t.charAt(j-1)) { sb.append(s.charAt(i-1)); i--; j--; }
        else if (dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }
    return sb.reverse().toString();
}

Interview Tips

The LCS recurrence is the basis for edit distance — know how to extend it.
LCS vs Longest Common Substring: LCS can skip characters (subsequence); substring must be contiguous.
Space optimization: since dp[i][j] only needs row i-1, you can use a single rolling row → O(n) space.

Longest Common Subsequence (LCS)

LCS is the foundational 2D DP problem. It appears directly in interviews and as a subroutine in edit distance, diff tools, and DNA sequence analysis.

LCS Definition

Given strings s and t, find the length of the longest subsequence common to both. A subsequence maintains relative order but doesn't need to be contiguous.

s = "ABCBDAB"
t = "BDCAB"
LCS = "BCAB" or "BDAB" → length 4

DP Solution

public int longestCommonSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m+1][n+1];
    // dp[i][j] = LCS length of s[0..i-1] and t[0..j-1]

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;      // match: extend LCS
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // no match: take best
            }
        }
    }
    return dp[m][n];
}

Time: O(m×n), Space: O(m×n), optimizable to O(min(m,n)).

Edit Distance (Levenshtein)

public int minDistance(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m+1][n+1];

    for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all of s
    for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all of t

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];               // no operation needed
            } else {
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],  // replace
                                Math.min(dp[i-1][j],    // delete from s
                                         dp[i][j-1]));  // insert into s
            }
        }
    }
    return dp[m][n];
}

Longest Common Substring (contiguous)

public int longestCommonSubstring(String s, String t) {
    int m = s.length(), n = t.length(), max = 0;
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1; // must be contiguous
                max = Math.max(max, dp[i][j]);
            }
            // else dp[i][j] = 0 (restart — subsequence breaks here)
        }
    }
    return max;
}

Shortest Common Supersequence

SCS = both strings as subsequences. Length = m + n - LCS(s,t).

public int shortestCommonSupersequence(String s, String t) {
    return s.length() + t.length() - longestCommonSubsequence(s, t);
}

Longest Palindromic Subsequence

// LPS of s = LCS(s, reverse(s))
public int longestPalindromicSubsequence(String s) {
    return longestCommonSubsequence(s, new StringBuilder(s).reverse().toString());
}

Reconstructing the LCS

public String reconstructLCS(String s, String t, int[][] dp) {
    StringBuilder sb = new StringBuilder();
    int i = s.length(), j = t.length();
    while (i > 0 && j > 0) {
        if (s.charAt(i-1) == t.charAt(j-1)) { sb.append(s.charAt(i-1)); i--; j--; }
        else if (dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }
    return sb.reverse().toString();
}

Interview Tips

The LCS recurrence is the basis for edit distance — know how to extend it.
LCS vs Longest Common Substring: LCS can skip characters (subsequence); substring must be contiguous.
Space optimization: since dp[i][j] only needs row i-1, you can use a single rolling row → O(n) space.