Practice/Google/Leetcode 1092. Shortest Common Supersequence

Leetcode 1092. Shortest Common Supersequence

CodingMust

Problem

Given two strings, find the shortest string that contains both input strings as subsequences. A subsequence is a sequence derived from another string by deleting some or no characters without changing the order of the remaining characters.

Your goal is to merge the two strings in a way that minimizes the total length while ensuring both original strings can be formed by removing characters from the result.

Requirements

1. Return the shortest possible string that contains both input strings as subsequences
2. If multiple valid answers exist with the same length, return any one of them
3. Both input strings consist only of lowercase English letters
4. The solution should preserve the relative order of characters from both input strings

Constraints

• 1 ≤ str1.length, str2.length ≤ 1000
• str1 and str2 consist of lowercase English letters only
• Expected time complexity: O(n × m) where n and m are the lengths of the input strings
• Expected space complexity: O(n × m)