Longest Common Subsequence

Description

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.

Example 2:
Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.

Example 3:
Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

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

Approach - Bottom Up 2D

• Check if character matches with both string then 1 + solve for subsequence with add 1 on both sides
• If do not matches then next subsequence from either side

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] d = new int[text1.length() + 1][text2.length() + 1];
        for (int i = text1.length() - 1; i >= 0; i--) {
            for (int j = text2.length() - 1; j >= 0; j--) {
                if (text1.charAt(i) == text2.charAt(j))
                    d[i][j] = 1 + d[i+1][j+1];
                else
                    d[i][j] = Math.max(d[i+1][j],d[i][j+1]);    
            }
        }
        return d[0][0];
    }
}

Approach - 1D

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() < text2.length()) {
            String t = text1;
            text1 = text2;
            text2 = t;
        }
        int[] d = new int[text2.length() + 1];
        for (int i = text1.length() - 1; i >= 0; i--) {
            int p = 0;
            for (int j = text2.length() - 1; j >= 0; j--) {
                int t = d[j];
                if (text1.charAt(i) == text2.charAt(j))
                    d[j] = 1 + p;
                else
                    d[j] = Math.max(d[j],d[j+1]);
                p = t;        
            }
        }
        return d[0];
    }
}

---

Primary Approach: 2D Bottom-Up Dynamic Programming ($O(M\times N)$ Time, $O(M\times N)$ Space)

Intuition

Define dp[i][j] as the length of the Longest Common Subsequence between the prefix text1[0 ... i-1] and text2[0 ... j-1]:

1. Base Case: If either string is empty (i = 0 or j = 0), dp[i][j] = 0.
2. Character Match (text1[i - 1] == text2[j - 1]): The matching character extends the LCS by 1:

$\text{dp}[i][j]=\text{dp}[i-1][j-1]+1$

3. Character Mismatch (text1[i - 1] != text2[j - 1]): We can either skip the character from text1 or text2:

$\text{dp}[i][j]=\max (\text{dp}[i-1][j],\text{dp}[i][j-1])$

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
 
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
 
                if (c1 == c2) {
                    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];
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Standard nested loop through both string lengths $M$ and $N$.
• Space Complexity: $O(M\times N)$ — Space used by the 2D matrix dp.

---

Alternative Approach: Space-Optimized DP ($O(M\times N)$ Time, $O(\min (M,N))$ Space)

Intuition

To compute row i of the DP table, we only ever need values from row i - 1 and the current row i.

1. Re-assign text2 to always be the shorter string so our DP array size is bounded by $\min (M,N)$.
2. Use two 1D arrays (prev and curr) or a single array dp updated left-to-right while maintaining prevDiag (which stores the old value of dp[j-1] from the previous row).

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // Ensure text2 is shorter to optimize space
        if (text1.length() < text2.length()) {
            return longestCommonSubsequence(text2, text1);
        }
 
        int m = text1.length();
        int n = text2.length();
        int[] dp = new int[n + 1];
 
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            int prevDiag = 0; // Represents dp[i-1][j-1]
 
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                int temp = dp[j]; // Store current dp[j] before overwriting
 
                if (c1 == c2) {
                    dp[j] = prevDiag + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
 
                prevDiag = temp; // Save for the next column calculation
            }
        }
 
        return dp[n];
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Same number of subproblem calculations.
• Space Complexity: $O(\min (M,N))$ auxiliary space — Only requires a single 1D array of length $\min (M,N)+1$.

---

Key Interview Discussion Points

• Reconstructing the String: If asked to return the actual string rather than just its length, trace backward from dp[m][n]:
  • If text1[i-1] == text2[j-1], append character to result and move to (i-1, j-1).
  • Otherwise, move toward the larger adjacent cell (dp[i-1][j] or dp[i][j-1]).
• Related String Problems: Mention that this subproblem forms the foundation for Delete Operation for Two Strings and Shortest Common Supersequence.

---

Easy Memory Rule

“Match $\to$ dp[i-1][j-1] + 1 | Mismatch $\to$ max(top, left)!”