Build a Shortest String Containing Two Subsequences
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Return a shortest string containing both str1 and str2 as subsequences. A subsequence keeps character order while allowing deletions. If several shortest strings work, any one is valid.
```cpp
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2);
};
```
### Examples
**Example 1:**
```text
Input: str1 = "ab", str2 = "ba"
Output: "aba"
Explanation: Both inputs occur as subsequences. Length2 would require the unequal inputs to be identical, so3 is optimal.
```
**Example 2:**
```text
Input: str1 = "aa", str2 = "b"
Output: "aab"
Explanation: Two a characters and one b are necessary and sufficient.
```
### Constraints
- Both input lengths are between 1 and 1000.
- Only lowercase English letters occur in either string.
### Contract considerations
Both strings must appear in order; shortest length is required but no lexicographic tie-break is imposed.
```hint Read the boundary condition
When several strings have minimum length, does the original task impose a lexicographic tie-break?
```
### What a Strong Answer Covers
Both strings must appear in order; shortest length is required but no lexicographic tie-break is imposed.
### Follow-up Questions
Optional practice extension, separate from the original task: How would you choose the lexicographically smallest answer among all shortest supersequences?
Overview: Build a Shortest String Containing Two Subsequences. Return a shortest string containing both str1 and str2 as subsequences.