DP-Interviews
  • Dynamic Programming
  • Notes
    • Equal Subset Sum Partition
    • Longest Increasing Subsequence
    • Maximum Ribbon Cut
    • Largest Divisible Subset
    • Longest Common Substring
    • Unbounded Knapsack
    • Minimum Coin Change
    • Coin Change
    • Target Sum
    • Minimum Subset Sum Difference
    • Rod Cutting
    • Longest Palindromic Substring
    • Longest Bitonic Sequence
    • Longest Repeating Sequence
    • Longest String Chain
    • Natarajan's Birthday Bombs
    • Subsequence Pattern Matching
    • Russian Doll
    • Buy & Sell Stock
    • Maximum Sum Increasing Subsequence
    • Longest Common Subsequence
    • Shortest Common Supersequence
    • 0/1 Knapsack Problem
    • Best Team With No Conflict
    • Count Subset Sum
    • Edit Distance
    • Box-Stacking
    • Longest Palindromic Subsequence
    • All Possible Cuts In All Possible Intervals For Choosing Last Operation
    • Minimum Deletions & Insertions To Transform a String into another
    • Regular Expression Matching
    • Wildcard Matching
    • Optimal Paths To Target
Powered by GitBook
On this page
  • Solution
  • Bottom-up DP

Was this helpful?

  1. Notes

Shortest Common Supersequence

PreviousLongest Common SubsequenceNext0/1 Knapsack Problem

Last updated 3 years ago

Was this helpful?

Given two sequences ‘s1’ and ‘s2’, write a method to find the length of the shortest sequence which has ‘s1’ and ‘s2’ as subsequences.

Example 1:

Input: s1: "abcf" s2:"bdcf"
Output: 5
Explanation: The shortest common super-sequence (SCS) is "abdcf".

Example 2:

Input: s1: "dynamic" s2:"programming"
Output: 15
Explanation: The SCS is "dynprogrammicng".

Solution

The problem is quite similar to the Longest Common Subsequence.

A basic brute-force solution could be to try all the super-sequences of the given sequences. We can process both of the sequences one character at a time, so at any step, we must choose between:

  1. If the sequences have a matching character, we can skip one character from both the sequences and make a recursive call for the remaining lengths to get SCS.

  2. If the strings don’t match, we start two new recursive calls by skipping one character separately from each string. The minimum of these two recursive calls will have our answer.

Bottom-up DP

Directly jumping to bottom up since it's so similar to LCS

Recursive Code
Bottom up Code