Longest Common Subsequence

Problem Statement

Given two strings, find the length of the longest subsequence that is common to both strings. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.

Example:

• Input: s1 = "ABCBDAB", s2 = "BDCAB"
• Output: 4 (LCS is "BCAB" or "BDAB")

Noob-Friendly Explanation

Imagine two playlists of songs. You want to find the longest list of songs that appear in both playlists in the same order (but not necessarily back-to-back). For example, if Playlist 1 is [A, B, C, B, D, A, B] and Playlist 2 is [B, D, C, A, B], the longest common ordered list is 4 songs long. The songs don't have to be next to each other — they just need to be in the same sequence.

Approach 1: Brute Force (Recursion)

Intuition

Compare characters from the end of both strings. If they match, they're part of the LCS. If not, try removing a character from each string and take the better result.

Algorithm

1. If either string is empty, return 0
2. If last characters match, return 1 + LCS of remaining
3. If they don't match, return max of (skip from s1, skip from s2)

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

        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return 1 + lcs(s1, s2, m - 1, n - 1);
        }

        return Math.max(
            lcs(s1, s2, m - 1, n),
            lcs(s1, s2, m, n - 1)
        );
    }
}

Complexity Analysis

• Time Complexity: O(2^(m+n)) - Each call can branch into 2 sub-calls
• Space Complexity: O(m + n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Build a 2D table where dp[i][j] is the LCS length of the first i characters of s1 and first j characters of s2. Fill it cell by cell using the same logic.

Algorithm

1. Create dp[m+1][n+1] initialized to 0
2. If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
3. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. Answer is dp[m][n]

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.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];
    }
}

Complexity Analysis

• Time Complexity: O(m * n) - Fill each cell of the m × n table
• Space Complexity: O(m * n) - The 2D DP table