310. LCS of Three Strings

Given three strings, find the length of their longest common subsequence - the longest sequence of characters (not necessarily contiguous) that appears, in the same relative order, in all three strings.

Input: Three lines: s1, s2, and s3. Output: Print a single integer - the length of the longest common subsequence shared by all three strings.

1 <= |s1|, |s2|, |s3| <= 100

This same generalization pattern extends further to LCS of FOUR or more strings, just adding another dimension each time - though the exponential growth in table size (and thus memory) makes this impractical much beyond 3 or 4 strings.

Find the length of the longest common subsequence shared among THREE strings. Brute force: Try every possible subsequence of s1 and check if it's ALSO a subsequence of both s2 and s3 - this is exponential (2^|s1| possible subsequences), completely impractical. Optimised: This is a DIRECT 3D generalization of the standard two-string LCS DP - the same core insight (matching characters extend the LCS, non-matching characters fall back to the best sub-problem after dropping one string's last character) simply extends naturally from 2 dimensions to 3.

Recursively try, for each trio of positions (i, j, k) into the three strings, whether the current characters match: if s1[i]==s2[j]==s3[k], recurse on (i+1,j+1,k+1) and add 1; otherwise recurse on all three ways of advancing exactly one pointer and take the maximum. This explores every possible way of aligning the three strings, but without caching, the same (i,j,k) state is recomputed many times through different recursive paths, leading to exponential blowup. Time: O(3^(n+m+p)) worst case Space: O(n+m+p) recursion depth

Build the same dp[i][j][k] table bottom-up in iterative loops instead of via recursion, filling smaller subproblems first. Since dp[i][j][k] only ever depends on the layer i-1 (and the current layer i), the full 3D table can be replaced with just two m x p layers that are swapped/reused as i advances, cutting memory roughly in half relative to storing the complete 3D table while keeping the same O(nmp) time. This matters because it removes both recursion overhead and the constant-factor cost of function calls, and reduces memory pressure at the given constraints. Time: O(n * m * p) Space: O(m * p)

Keep the exact same recurrence as brute force, but store the result of each (i, j, k) state in a 3D memo table the first time it's computed, and return the cached value immediately on subsequent calls. Since each state now does O(1) work beyond its recursive calls (all of which are also memoized), the total work is bounded by the number of distinct states rather than the number of recursive calls, eliminating the exponential recomputation. Time: O(n * m * p) Space: O(n * m * p)

1. dp[i][j][k] = LCS length of the first i characters of s1, first j of s2, and first k of s3. 2. If s1[i-1]==s2[j-1]==s3[k-1], dp[i][j][k]=dp[i-1][j-1][k-1]+1. 3. Otherwise, take the MAX of dropping the last character from any ONE of the three strings: dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1].

Time: O(|s1| * |s2| * |s3|) - filling the 3D DP table, one cell per triple of positions. Space: O(|s1| * |s2| * |s3|) for the full table (reducible with a rolling 2D array over the outermost dimension).

Test strings with no character in common (LCS length 0), single-character strings, and all three strings at the maximum length 100 for the O(n^3) DP's performance.

Be ready to explain the direct generalization from 2-string to 3-string LCS clearly - recognizing that the SAME recurrence idea just adds one more dimension is a strong signal of genuinely understanding the underlying DP principle, not just memorizing the 2-string formula.