hardDynamic Programming 2DPure DSA~40 min
Shortest Merged Changelog Preserving Both Orders
Two release changelogs list event codes in order. You want the shortest single changelog that contains BOTH as subsequences — so replaying it reproduces either release's sequence by skipping the other's extra entries.
Problem
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, return any.
Input
Two strings str1 and str2.
Output
A shortest common supersequence of the two strings.
Constraints
- 1 ≤ |str1|, |str2| ≤ 1000
- Lowercase English letters.
Examples
Example 1
Input
str1="abac" str2="cab"
Output
cabac
'cabac' contains 'abac' (positions 1,2,3,4) and 'cab' (positions 0,1,2).
Example 2
Input
str1="abc" str2="abc"
Output
abc
Identical strings — the supersequence is the string itself.