216. Shortest Common Supersequence Length

Given two strings, find the length of the shortest string that has both of them as subsequences.

Input: Two lines: the first contains s1, the second contains s2. Output: Print a single integer - the length of the shortest common supersequence of s1 and s2.

1 <= |s1|, |s2| <= 1000

This problem only asks for the LENGTH, not the actual supersequence string itself - if the ACTUAL string were required, you'd need to additionally reconstruct it by tracing back through the LCS DP table, a meaningfully harder follow-up.

Find the length of the shortest string that contains both given strings as subsequences. Brute force: Try every possible way of interleaving/merging the two strings and check the shortest one containing both as subsequences - this is exponential to search directly, when the elegant LCS-based formula computes the answer with a single DP pass. Optimised: The insight that OVERLAPPING characters (those in the LCS) never need to be duplicated in the merged supersequence - they can serve BOTH strings' subsequence requirement simultaneously - reduces this seemingly separate problem to a simple arithmetic formula built directly on top of the well-known LCS DP.

The key insight is that the shortest common supersequence length equals |s1| + |s2| minus the length of the Longest Common Subsequence (LCS) of s1 and s2 - every character that appears in the LCS only needs to be written once, while every other character from both strings must appear separately. This turns the problem into the classic LCS dynamic programming problem: build a table dp[i][j] representing the LCS length of s1[0..i) and s2[0..j), filling it in using the same match/no-match recurrence as the brute force, but computing each state exactly once instead of recomputing it. This avoids the exponential blowup entirely. Time: O(m*n) Space: O(m*n)

The LCS DP table only ever needs the previous row to compute the current row, so the full 2D table can be collapsed to two 1D rows (or even one row updated carefully) that are reused as the computation moves down through s1's characters. This keeps the exact same O(m*n) work and correctness as the full-table DP, but reduces the memory footprint from quadratic to linear in the shorter string's length, which matters when both strings can be 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 either string is exhausted, the answer is the length of whatever remains of the other one. If the current characters match, they can be shared in the supersequence, so take that character and recurse on both shorter suffixes. If they don't match, one of the two characters must still appear next, so try including s1's character (recurse with s1 advanced) or s2's character (recurse with s2 advanced) and keep the cheaper option, adding 1 for the character used. This tries every possible way of interleaving the two strings, so it is correct, but the same (i, j) suffix pair gets recomputed exponentially many times. Time: O(2^(m+n)) Space: O(m+n)

1. Compute the LCS (Longest Common Subsequence) length of the two strings with the standard DP. 2. The shortest common supersequence's length equals |s1| + |s2| - LCS(s1,s2) - every character in their longest common subsequence only needs to appear ONCE in the merged result, instead of once per string. 3. Apply this formula directly once the LCS length is known.

Time: O(|s1| * |s2|) - dominated by computing the LCS length via standard DP. Space: O(|s1| * |s2|) for the LCS DP table (reducible to O(min(|s1|,|s2|)) with a rolling array).

Test strings with no characters in common (LCS = 0, so the answer is just |s1| + |s2|), identical strings, and both strings at the maximum length 1000 for O(n*m) DP performance.

Be ready to derive the formula |s1|+|s2|-LCS explicitly with a small example - this connects two seemingly separate string DP problems (LCS and shortest common supersequence) through one elegant relationship.