Grokking Dynamic Programming Patterns for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Shortest Common Super-sequence
On this page

Problem Statement

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 2:

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".

Constraints:

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of lowercase English letters.

Basic Solution

The problem is quite similar to the `"Longest Common Subsequence"

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page