DiffPush Tier Dynamic Programming · DP on Strings O(n*m) · O(n*m)
A radio network must interleave two station playlists into one master broadcast so that every song of each playlist still airs in its original relative order. Ad space is expensive, so the merged reel must be as short as possible. Several optimal reels may exist; any shortest merge is acceptable.
Input: Two strings str1 and str2.
Output: Return any shortest merged string that embeds both inputs as in-order character sequences.
1 <= len(str1), len(str2) <= 1000strings consist of lowercase English lettersInput: {"str1":"abac","str2":"cab"}
Output: "cabac"
"cabac" contains "abac" (positions 2-5) and "cab" (positions 1-3); no shorter merge exists.
Input: {"str1":"abc","str2":"abc"}
Output: "abc"
Identical strings merge into themselves.