Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 1092 Shortest Common Supersequence - The LCS Connection

Length formula

The length of SCS relates directly to LCS: SCS=A+BLCS|SCS| = |A| + |B| - |LCS| Why? The LCS appears once in the supersequence. Everything else from A and B must be added. You add ALCS|A| - |LCS| characters from A and BLCS|B| - |LCS| characters from B. Total: LCS+(ALCS)+(BLCS)=A+BLCS|LCS| + (|A| - |LCS|) + (|B| - |LCS|) = |A| + |B| - |LCS|.

To construct the actual string, you need to backtrack through the LCS DP table.