Shortest Common Supersequence
DP on Strings DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Shortest Common Supersequence Problem, Dynamic Programming, Longest Common Subsequence, Subsequences, Strings, Time Complexity, Space Complexity, Tabulation, String Manipulation, dynamic programming, Longest Common Subsequence (LCS).
Problem Statement Given two strings S1 and S2, find their shortest common supersequence. A supersequence is defined as a string which contains both S1 and S2 as subsequences. Example: S1 = "brute" S2 = "groot" Output: "bgruoote" Explanation: S1 ("brute") is a subsequence of "bgruoote". S2 ("groot") is a subsequence of "bgruoote". No shorter string exists that contains both S1 and S2 as subsequences. Input Specification: The input will consist of two strings, S1 and S2. Output Specification: Return the shortest common supersequence string.