Printing Longest Common Subsequence

Problem: Print Longest Common Subsequence

Link: Print Longest Common Subsequence (Conceptual)

Given two strings s1 and s2, print the longest common subsequence (LCS) between them.

Intuition

• A subsequence appears in the same relative order but not necessarily contiguous.

• At each index, we either take the matching character or move forward by skipping one.

• The idea is to explore both options and choose the one that gives the longest result.

IBH Format

• I (Induction): Parameters i and j represent indices in s1 and s2.

• B (Base Case): If either index becomes 0, return 0 (no characters left).

• H (Hypothesis):

  • If characters match, take 1 + result of i-1, j-1.

  • If they don’t match, take the max of skipping one character from either string.

1. Recursion

public class Solution {
    public int lcs(int i, int j, String s1, String s2) {
        if (i == 0 || j == 0) return 0;

        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return 1 + lcs(i - 1, j - 1, s1, s2);
        } else {
            return Math.max(
                lcs(i - 1, j, s1, s2),
                lcs(i, j - 1, s1, s2)
            );
        }
    }

    public int longestCommonSubsequence(String s1, String s2) {
        return lcs(s1.length(), s2.length(), s1, s2);
    }
}

• Time Complexity: Exponential

• Space Complexity: O(n + m) recursion stack

2. Memoization

public class Solution {
    public int lcs(int i, int j, String s1, String s2, int[][] dp) {
        if (i == 0 || j == 0) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return dp[i][j] = 1 + lcs(i - 1, j - 1, s1, s2, dp);
        } else {
            return dp[i][j] = Math.max(
                lcs(i - 1, j, s1, s2, dp),
                lcs(i, j - 1, s1, s2, dp)
            );
        }
    }

    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        return lcs(n, m, s1, s2, dp);
    }
}

• Time Complexity: O(n * m)

• Space Complexity: O(n * m) + recursion stack

3. Tabulation

public class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][m];
    }
}

• Time Complexity: O(n * m)

• Space Complexity: O(n * m)

4. Printing the LCS

public class Solution {
    public String printLCS(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];

        // Build the dp table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Trace back to get the LCS string
        StringBuilder lcs = new StringBuilder();
        int i = n, j = m;

        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                lcs.append(s1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return lcs.reverse().toString();
    }
}

Example

Input:
s1 = "abcde", s2 = "ace"

Output:
LCS = "ace"

Summary Table