Facebook Pixel

You are on level: Student

0%
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section

Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that contains both of them as subsequences.

A string contains another as a subsequence when the second can be obtained by deleting zero or more characters from the first without reordering the rest. Concatenating the two inputs always produces a supersequence; the task is to find the shortest one.

Input & Output
Input
str1 — the first string that must appear as a subsequence
str2 — the second string that must appear as a subsequence
Output
the shortest string containing both str1 and str2 as subsequences
Example
Input
str1 = "abac", str2 = "cab"
Output
"cabac"
Explanation

Deleting the leading c from "cabac" leaves "abac", and deleting the b and the final c leaves "cab". No string of length 4 contains both, and "cabac" is the only string of length 5 that does.

Example
Input
str1 = "abcde", str2 = "ace"
Output
"abcde"
Explanation

"ace" is already a subsequence of "abcde", so nothing has to be added and the longer string is itself the answer.

Constraints
  • 1 <= str1.length, str2.length <= 1000
  • str1 and str2 consist of lowercase English letters
  • Each test case has exactly one shortest common supersequence, so the answer is compared as an exact string

Try it yourself

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro