Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Home
Talentd Logo
Talentd

Your trusted platform to ace any job interviews, craft the perfect resumes, and land your dream jobs.

P
Featured on
Product Hunt
▲455
All services are online

Products

  • Resume Review
  • Company Prep Pack
  • DSA Corner
  • Jobs
  • Internships
  • Fresher Jobs
  • Roadmaps
  • Tax Calculator

Resources

  • Articles
  • DRDO Internships

Support

  • Contact Us

DSA & Interview Prep

  • DSA Questions
  • DSA Sheets
  • Company Questions
  • Topics

Company

  • Companies Hiring
  • About
  • Contact
  • Advertisement

Legal

  • Privacy Policy
  • Terms & Conditions
  • Refund Policy
  • Delivery Policy

Popular Skills

Browse All Skills →

Popular Tags

Browse All Tags →

© 2025 Talentd.in - All rights reserved

Privacy PolicyTerms & Conditions
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
DSA Corner
DashboardQuestionsTopicsCompaniesSheets

Talentd Logo
Talentd

Your trusted platform to ace any job interviews, craft the perfect resumes, and land your dream jobs.

P
Featured on
Product Hunt
▲455
All services are online

Products

  • Resume Review
  • Company Prep Pack
  • DSA Corner
  • Jobs
  • Internships
  • Fresher Jobs
  • Roadmaps
  • Tax Calculator

Resources

  • Articles
  • DRDO Internships

Support

  • Contact Us

DSA & Interview Prep

  • DSA Questions
  • DSA Sheets
  • Company Questions
  • Topics

Company

  • Companies Hiring
  • About
  • Contact
  • Advertisement

Legal

  • Privacy Policy
  • Terms & Conditions
  • Refund Policy
  • Delivery Policy

Popular Skills

Browse All Skills →

Popular Tags

Browse All Tags →

© 2025 Talentd.in - All rights reserved

Privacy PolicyTerms & Conditions
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
DSA Corner
DashboardQuestionsTopicsCompaniesSheets
Talentd Logo
Talentd

Your trusted platform to ace any job interviews, craft the perfect resumes, and land your dream jobs.

P
Featured on
Product Hunt
▲455
All services are online

Products

  • Resume Review
  • Company Prep Pack
  • DSA Corner
  • Jobs
  • Internships
  • Fresher Jobs
  • Roadmaps
  • Tax Calculator

Resources

  • Articles
  • DRDO Internships

Support

  • Contact Us

DSA & Interview Prep

  • DSA Questions
  • DSA Sheets
  • Company Questions
  • Topics

Company

  • Companies Hiring
  • About
  • Contact
  • Advertisement

Legal

  • Privacy Policy
  • Terms & Conditions
  • Refund Policy
  • Delivery Policy

Popular Skills

Browse All Skills →

Popular Tags

Browse All Tags →

© 2025 Talentd.in - All rights reserved

Privacy PolicyTerms & Conditions
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
DSA Corner
DashboardQuestionsTopicsCompaniesSheets
Talentd Logo
Talentd

Your trusted platform to ace any job interviews, craft the perfect resumes, and land your dream jobs.

P
Featured on
Product Hunt
▲455
All services are online

Products

  • Resume Review
  • Company Prep Pack
  • DSA Corner
  • Jobs
  • Internships
  • Fresher Jobs
  • Roadmaps
  • Tax Calculator

Resources

  • Articles
  • DRDO Internships

Support

  • Contact Us

DSA & Interview Prep

  • DSA Questions
  • DSA Sheets
  • Company Questions
  • Topics

Company

  • Companies Hiring
  • About
  • Contact
  • Advertisement

Legal

  • Privacy Policy
  • Terms & Conditions
  • Refund Policy
  • Delivery Policy

Popular Skills

Browse All Skills →

Popular Tags

Browse All Tags →

© 2025 Talentd.in - All rights reserved

Privacy PolicyTerms & Conditions
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
Jobs
Learning
Career Tools
Talentd Logo
Talentd#1 Freshers Platform
DSA Corner
DashboardQuestionsTopicsCompaniesSheets
Back to Problems

1092. Shortest Common Supersequence

Hard59.6% Acceptance
StringDynamic Programming
Asked by:
A
Amazon
Bloomberg
ProblemHints (2)SolutionsVideosCompanies (5)Notes

Problem Statement

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

Constraints:

  • 1 <= str1.length, str2.length <= 1000
  • str1 and str2 consist of lowercase English letters.
Talentd Logo
Talentd

Your trusted platform to ace any job interviews, craft the perfect resumes, and land your dream jobs.

P
Featured on
Product Hunt
▲455
All services are online

Products

  • Resume Review
  • Company Prep Pack
  • DSA Corner
  • Jobs
  • Internships
  • Fresher Jobs
  • Roadmaps
  • Tax Calculator

Resources

  • Articles
  • DRDO Internships

Support

  • Contact Us

DSA & Interview Prep

  • DSA Questions
  • DSA Sheets
  • Company Questions
  • Topics

Company

  • Companies Hiring
  • About
  • Contact
  • Advertisement

Legal

  • Privacy Policy
  • Terms & Conditions
  • Refund Policy
  • Delivery Policy

Popular Skills

Browse All Skills →

Popular Tags

Browse All Tags →

© 2025 Talentd.in - All rights reserved

Privacy PolicyTerms & Conditions
B
G
Google
M
Microsoft
U
Uber

Approach

The Shortest Common Supersequence (SCS) of two strings is the shortest string that contains both strings as subsequences. A key insight is the strong relationship between SCS and the Longest Common Subsequence (LCS). If we know the LCS, we can merge the remaining characters from both strings while preserving order.

A common strategy is to first compute the LCS using Dynamic Programming. Build a DP table where dp[i][j] represents the length of the LCS for prefixes of the two strings. Once the table is filled, we can reconstruct the shortest supersequence by walking backward through the table and appending characters appropriately when they match or differ.

This approach ensures that common characters are not duplicated, keeping the resulting string minimal. The DP computation takes O(n × m) time, and reconstructing the supersequence also follows the same grid traversal with O(n × m) space usage.

Complexity

ApproachTime ComplexitySpace Complexity
Dynamic Programming using LCS tableO(n × m)O(n × m)
Reconstructing the Shortest Common SupersequenceO(n + m)O(n × m)

Video Solution Available

take U forward

View all video solutions

Problem Hints

Use these hints if you're stuck. Try solving on your own first.

1
Hint 1

We can find the length of the longest common subsequence between str1[i:] and str2[j:] (for all (i, j)) by using dynamic programming.

2
Hint 2

We can use this information to recover the shortest common supersequence.

Ready to see the solutions?View Solutions

Solutions

No Solutions Yet

Official solutions haven't been published for this problem yet.

View on LeetCode

Video Solutions

Watch expert explanations and walkthroughs

DP 31. Shortest Common Supersequence | DP on Strings

take U forward
26:44199,680 views

Asked By Companies

5 companies
A
Amazon
B
Bloomberg
G
Google
M
Microsoft
U
Uber

Prepare for Interviews

Practice problems asked by these companies to ace your technical interviews.

Explore More Problems

Notes

Personal Notes

Jot down your thoughts, approach, and key learnings

0 characters

Similar Problems

Longest Palindromic SubstringMedium
Regular Expression MatchingHard
Generate ParenthesesMedium
Longest Valid ParenthesesHard
More similar problems

Related Topics

StringDynamic Programming

Problem Stats

Acceptance Rate59.6%
DifficultyHard
Companies5

Practice on LeetCode

Solve with full IDE support and test cases

Solve Now

Frequently Asked Questions

Is Shortest Common Supersequence asked in FAANG interviews?

Yes, variations of the Shortest Common Supersequence problem frequently appear in FAANG and other top tech interviews. It tests understanding of dynamic programming, string manipulation, and the relationship between LCS and SCS.

What data structure is best for Shortest Common Supersequence?

A 2D dynamic programming table is typically used to compute the LCS between the two strings. This table helps track overlapping subproblems and is later used to reconstruct the shortest common supersequence efficiently.

What is the optimal approach for Shortest Common Supersequence?

The optimal approach uses Dynamic Programming based on the Longest Common Subsequence (LCS). By first computing the LCS table, you can reconstruct the shortest supersequence by merging characters from both strings while avoiding duplicates.

Why is LCS important for solving Shortest Common Supersequence?

The LCS represents characters common to both strings in order. By identifying this shared subsequence, we can avoid repeating those characters when building the supersequence, ensuring the final string remains as short as possible.