LCS (Longest Common Subsequence) of three strings

Problem Statement

Given three strings, find the length of the longest common subsequence present in all three of them.

Example:

• Input: s1 = "geeks", s2 = "geeksfor", s3 = "geeksforgeeks"
• Output: 5 (LCS is "geeks")

Noob-Friendly Explanation

You know the LCS problem for two strings? Now imagine you have three playlists, and you want the longest list of songs that appears in all three in the same order. It's the same idea, just extended to 3 dimensions. If the three playlists share "geeks" as a common ordered subsequence, and that's the longest one, the answer is 5.

Approach 1: Brute Force (Recursion)

Intuition

Compare the last character of all three strings. If all three match, it's part of the LCS. Otherwise, try reducing each string by one character and take the best result.

Algorithm

1. If any string is empty, return 0
2. If all three last characters match, return 1 + LCS of the rest
3. Otherwise, try all three options of reducing one string and take the max

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

        if (s1.charAt(l - 1) == s2.charAt(m - 1)
            && s2.charAt(m - 1) == s3.charAt(n - 1)) {
            return 1 + lcsOf3(s1, s2, s3, l - 1, m - 1, n - 1);
        }

        return Math.max(
            lcsOf3(s1, s2, s3, l - 1, m, n),
            Math.max(
                lcsOf3(s1, s2, s3, l, m - 1, n),
                lcsOf3(s1, s2, s3, l, m, n - 1)
            )
        );
    }
}

Complexity Analysis

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

Approach 2: Optimal (3D Bottom-Up DP)

Intuition

Extend the 2D LCS table to 3D. dp[i][j][k] stores the LCS length of the first i chars of s1, first j chars of s2, and first k chars of s3.

Algorithm

1. Create dp[l+1][m+1][n+1] initialized to 0
2. If all three characters match: dp[i][j][k] = dp[i-1][j-1][k-1] + 1
3. Else: dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
4. Answer is dp[l][m][n]

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

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

        return dp[l][m][n];
    }
}

Complexity Analysis

• Time Complexity: O(l * m * n) - Three nested loops
• Space Complexity: O(l * m * n) - 3D DP table