Theory - Longest Common Subsequence

1. Problem Definition

Formal Problem Statement

Given two strings s1 and s2, find the length of their longest common subsequence (LCS).

What is a Subsequence?

• A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

• Key difference from substring: Elements don't need to be contiguous.

Examples

Example 1:

• s1 = "abcde", s2 = "ace"

• LCS = "ace" (length = 3)

Example 2:

• s1 = "abc", s2 = "def"

• LCS = "" (length = 0)

Example 3:

• s1 = "abcdgh", s2 = "aedfhr"

• LCS = "adh" (length = 3)

2. Recursive Intuition

Basic Recursion Logic

Start from the end of both strings with two pointers i and j.

Two Choices at Each Step

If s1[i] == s2[j]:
    PICK: Include this character in LCS
    → 1 + LCS(i-1, j-1)

Else:
    DON'T PICK: Explore both possibilities
    → max(LCS(i-1, j), LCS(i, j-1))

Pick/Not-Pick Strategy Table

3. Recursive Tree Diagram

For s1 = "abcde" and s2 = "ace":

                    LCS(4,2) [e vs e]
                         |
                    1 + LCS(3,1) [d vs c]
                         |
                   max(LCS(2,1), LCS(3,0))
                        /              \
                  LCS(2,1)           LCS(3,0)
                  [c vs c]           [d vs a]
                     |                  |
                1 + LCS(1,0)       max(LCS(2,0), LCS(3,-1))
                     |                  |
                  LCS(1,0)           LCS(2,0)
                  [b vs a]           [c vs a]
                     |                  |
               max(LCS(0,0), LCS(1,-1)) ...

Observations:

• Exponential branching

• Repeated subproblems

• Time Complexity: O(2^(n+m))

4. Base Case + Choice Diagram

Base Cases

if (i < 0 || j < 0) {
    return 0;
}

Choice Diagram Flowchart

      Start: LCS(i, j)
           |
      s1[i] == s2[j]?
          /        \
        YES          NO
         |            |
    1 + LCS(i-1,j-1)  |
                      |
               max(LCS(i-1,j), LCS(i,j-1))

5. Memoization (Top-Down DP)

Code Implementation

public class LCSMemoization {
    
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        
        return solve(s1, s2, n-1, m-1, dp);
    }
    
    private int solve(String s1, String s2, int i, int j, int[][] dp) {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        if (s1.charAt(i) == s2.charAt(j)) {
            dp[i][j] = 1 + solve(s1, s2, i-1, j-1, dp);
        } else {
            dp[i][j] = Math.max(
                solve(s1, s2, i-1, j, dp),
                solve(s1, s2, i, j-1, dp)
            );
        }
        return dp[i][j];
    }
}

Complexity

• Time: O(n × m)

• Space: O(n × m) + O(n + m)

6. Tabulation (Bottom-Up DP)

State Definition

dp[i][j] = LCS of s1[0...i-1] and s2[0...j-1]

Code

public class LCSTabulation {
    
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length();
        int 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];
    }
}

Complexity

• Time: O(n × m)

• Space: O(n × m)

7. Space Optimization

Code (Two Arrays)

public class LCSSpaceOptimized {
    
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[] prev = new int[m+1];
        int[] curr = new int[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)) {
                    curr[j] = 1 + prev[j-1];
                } else {
                    curr[j] = Math.max(prev[j], curr[j-1]);
                }
            }
            prev = curr.clone();
        }
        return prev[m];
    }
}

Code (Single Array)

public int longestCommonSubsequenceOptimal(String s1, String s2) {
    if (s1.length() < s2.length()) {
        return longestCommonSubsequenceOptimal(s2, s1);
    }
    
    int n = s1.length(), m = s2.length();
    int[] dp = new int[m+1];
    
    for (int i = 1; i <= n; i++) {
        int prev = 0;
        for (int j = 1; j <= m; j++) {
            int temp = dp[j];
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[j] = 1 + prev;
            } else {
                dp[j] = Math.max(dp[j], dp[j-1]);
            }
            prev = temp;
        }
    }
    return dp[m];
}

8. Reconstructing the LCS String

Code

public class LCSStringReconstruction {
    
    public String longestCommonSubsequence(String s1, String s2) {
        int n = s1.length();
        int 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]);
                }
            }
        }
        
        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();
    }
}

9. Real Interview Problems Based on LCS

LCS Variants

1. Longest Palindromic Subsequence

2. Shortest Common Supersequence

3. Min Insertions/Deletions

4. Edit Distance

5. Subsequence Pattern Matching

6. Print All LCS

7. LCS of Three Strings

8. Longest Repeating Subsequence

9. Max Sum Increasing Subsequence

10. Longest Common Substring

10. Summary

Approach Comparison

Interview Strategy

Identify Patterns:

• "Longest", "Common", "Subsequence"

• Transform/Convert problems

• Palindrome → LCS of string and reverse

Step-by-Step Plan:

1. Start with recursion (show logic)

2. Add memoization (optimize)

3. Mention tabulation

4. Optimize space if needed

5. Implement string reconstruction if asked