Skills101
← All coding problems

Shortest Common Supersequence Length

mediumDynamic Programming II+20 XPTime limit 3s

Two DNA fragments a and b must both be found inside one longer strand as subsequences (their letters appear in order, not necessarily next to each other). What is the length of the shortest strand that contains both?

Input: two lines: the strings a and b.

Output: the length of the shortest common supersequence.

Constraints: 1 ≤ length of a, b ≤ 1000; lowercase letters.

Example: for abac and cab, cabac works, so the answer is 5.

Think about it: letters shared by both strings can be written once if they line up in order — the most you can share is their longest common subsequence. So the answer is |a| + |b| − LCS(a, b), with the O(|a| · |b|) LCS table.

Sample input 1

abac
cab

Sample output 1

5

Sample input 2

geek
eke

Sample output 2

5

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.