68. Longest Common Subsequence

Given two strings s1 and s2, find the length of their longest common subsequence (a sequence that appears, in order but not necessarily contiguously, in both strings).

Input: The first line contains string s1. The second line contains string s2. Output: Print a single integer - the length of the longest common subsequence of s1 and s2.

0 <= |s1|, |s2| <= 1000

LCS is about a subsequence (characters don't need to be contiguous), which is a subtly different and generally HARDER problem than 'longest common SUBSTRING' (which does require contiguity) - keeping this distinction crystal clear avoids a very common mix-up.

Given two strings, find the length of the longest sequence of characters that appears in both, in the same relative order, but not necessarily touching each other. Brute force: Try every possible subsequence of s1 and check if it's also a subsequence of s2 - this is exponential (2^n possible subsequences of s1), completely impractical for anything beyond tiny strings. Optimised: The DP table captures exactly the reusable insight that the LCS of two PREFIXES only depends on the LCS of slightly shorter prefixes - filling the table bottom-up (or via memoized recursion) computes every needed sub-answer exactly once, turning exponential exploration into a table of (|s1|+1)*(|s2|+1) cells.

Build the DP table iteratively from the smallest subproblems upward: dp[i][j] is dp[i-1][j-1] + 1 if s1[i-1] == s2[j-1], otherwise max(dp[i-1][j], dp[i][j-1]). Since each row only ever depends on the row directly above it, only two rows (or one row updated carefully) need to be kept in memory at once instead of the full table, cutting space from O(m*n) down to O(min(m, n)) while keeping the same O(m*n) time - a genuine space optimization over the memoized version, which is important given strings up to length 1000. Time: O(m * n) Space: O(min(m, n))

Define a recursive function on the two remaining suffixes of s1 and s2: if the last characters match, the answer is 1 plus the LCS of both strings without their last character; otherwise it's the maximum of dropping the last character of either string. Trying every branch of this recursion without remembering repeated subproblems explores an exponential number of overlapping calls, so it is correct but explodes combinatorially even for modest string lengths. Time: O(2^(m+n)) Space: O(m + n)

Keep the exact same recursive structure as the brute force, but cache the result for each distinct (i, j) pair of suffix lengths in a memo table before returning it, and check the cache before recomputing. Since there are only O(m*n) distinct subproblems, memoization collapses the exponential recursion tree down to polynomial time by ensuring each subproblem is solved once, at the cost of an O(m*n) table plus recursion stack. Time: O(m * n) Space: O(m * n)

1. Build a 2D DP table where dp[i][j] means 'the LCS length of the first i characters of s1 and the first j characters of s2'. 2. If the current characters (s1[i-1] and s2[j-1]) match, extend the best subsequence found without either of them by 1: dp[i][j] = dp[i-1][j-1] + 1. 3. If they don't match, take the better of skipping a character from either string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Time: O(|s1| * |s2|) - filling the entire DP table, one cell per pair of prefix lengths. Space: O(|s1| * |s2|) for the full table (though this can be reduced to O(min(|s1|,|s2|)) using a rolling array, since each row only depends on the row directly above it).

Either string empty (LCS length 0, since the constraint allows |s1| or |s2| = 0); s1 and s2 identical (LCS equals the full length); no characters in common at all; strings up to length 1000 each for performance.

This is one of THE most foundational DP problems in all of interviewing - it underlies diff tools, version control merge algorithms, and DNA sequence comparison, and is worth being able to derive the recurrence for from scratch, not just memorize.