Dynamic Programming21 sections · 915 units
Open in Course

LeetCode 1092 Shortest Common Supersequence - The LCS Connection

Length formula

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

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