Show problems as
Classic problem #1092HardStringDynamic ProgrammingLongest Common Subsequence

Shortest Common Supersequence

Real-world version: The Shortest Tape Holding Both Readings
Tracked in this browser only
Read Shortest Common Supersequence on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two readings of lowercase letters are given, first and second. A tape holds a reading when deleting some of the tape's letters, possibly none of them, leaves that reading exactly.

Return the shortest tape that holds both readings. Where several tapes tie for shortest, return the one that comes first in dictionary order.

Examples

Example 1

Input
first = "bcd", second = "abc"
Output
"abcd"

The tape holds the first reading once its opening letter is dropped and the second once its closing letter is dropped. Nothing shorter works, since the two readings share only the letters b and c.

Example 2

Input
first = "abc", second = "def"
Output
"abcdef"

The two readings share no letter at all, so the tape has to hold all six. Writing the first reading before the second comes earlier in dictionary order than the other way round.

Example 3

Input
first = "ab", second = "ba"
Output
"aba"

Three letters are needed, since the readings share only one letter in common. Both possible tapes work, and the one opening on a comes first in dictionary order.

Constraints

  • 1 <= first.length <= 1000
  • 1 <= second.length <= 1000
  • Both readings are made of lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shortest_common_supersequence(first: str, second: str) -> str:
Java
public String shortestCommonSupersequence(String first, String second)

More on the same topics