Shortest Common Supersequence · Interview Problem

Back to problems

Leetcode

Medium

DP on Strings

Strings

Dynamic Programming

Google

Microsoft

Shortest Common Supersequence

Find the shortest string that contains two given strings as subsequences.

Acceptance 33%

Start Practice

Problem Statement

Problem

Given two strings str1 and str2, return the shortest common supersequence (SCS) of the two strings.

A string is a supersequence of another string if it can be formed by inserting characters anywhere in the original string without changing the order of the existing characters.

Your task is to construct a string with minimum possible length such that both str1 and str2 are subsequences of it.

If there are multiple answers, you may return any one of them.

Notes

A subsequence does not need to be contiguous.
The answer should preserve the relative order of characters from both input strings.
The shortest solution is typically built using dynamic programming over prefixes of the two strings.

Input Format

Two strings str1 and str2.
Each string consists of lowercase English letters.

Output Format

Return one shortest common supersequence of str1 and str2 as a string.

Constraints

1 <= str1.length, str2.length <= 1000
str1 and str2 contain only lowercase English letters
If multiple shortest answers exist, return any one

Examples

Sample cases returned by the problem API.

Example 1

Input

str1 = "abac"
str2 = "cab"

Output

"cabac"

Explanation

Both strings are subsequences of "cabac", and no shorter valid supersequence exists.

Example 2

Input

str1 = "geek"
str2 = "eke"

Output

"geeke"

Explanation

"geeke" contains both "geek" and "eke" as subsequences and has minimum length.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress