Shortest Common Supersequence
HardPrompt
Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.
A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.
Example 1:
Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.Example 2:
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"
Constraints:
1 <= str1.length, str2.length <= 1000str1andstr2consist of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward recursive method to solve the problem. It breaks down the problem into smaller subproblems by considering the first characters of the two strings. While simple to conceptualize, it suffers from massive performance issues due to re-calculating solutions for the same pairs of substrings multiple times.
Algorithm
- Define a recursive function, say
solve(s1, s2), that takes two strings and returns their shortest common supersequence. - Base Case: If either string is empty, the SCS is simply the other non-empty string. Return it.
- Recursive Step:
- If the first characters of
s1ands2are the same (s1[0] == s2[0]): The common character can be used once. The result is this character prepended to the result of the recursive call on the rest of the strings:s1[0] + solve(s1.substring(1), s2.substring(1)). - If the first characters are different: We have two possibilities to form the supersequence.
- Include
s1[0]in the supersequence and find the SCS of the rest ofs1and all ofs2. Result:s1[0] + solve(s1.substring(1), s2). - Include
s2[0]in the supersequence and find the SCS of all ofs1and the rest ofs2. Result:s2[0] + solve(s1, s2.substring(1)).
- Include
- Compare the lengths of the two resulting strings from the above step and return the shorter one.
- If the first characters of
Walkthrough
The core idea is to build the shortest common supersequence (SCS) character by character from the beginning. At each step, we compare the first characters of the current substrings of str1 and str2.
If the characters match, we know this character must be in the SCS. We add it to our result and proceed to find the SCS for the remaining parts of both strings.
If the characters do not match, we have a choice. We can either take the character from str1 and find the SCS for the rest of str1 and the entirety of str2, or we can take the character from str2 and find the SCS for str1 and the rest of str2. To ensure the final supersequence is the shortest, we recursively explore both paths and choose the one that yields a shorter result.
This method naturally leads to a recursive structure but creates an explosion of function calls for the same subproblems, making it impractical for the given constraints.
// Note: This solution is for demonstration and will Time Limit Exceed.class Solution { public String shortestCommonSupersequence(String str1, String str2) { // Base case: if one string is empty, the other is the SCS. if (str1.isEmpty()) { return str2; } if (str2.isEmpty()) { return str1; } // If first characters are the same, they contribute one char to SCS. if (str1.charAt(0) == str2.charAt(0)) { return str1.charAt(0) + shortestCommonSupersequence(str1.substring(1), str2.substring(1)); } else { // If different, explore two paths and choose the shorter result. String res1 = str1.charAt(0) + shortestCommonSupersequence(str1.substring(1), str2); String res2 = str2.charAt(0) + shortestCommonSupersequence(str1, str2.substring(1)); if (res1.length() < res2.length()) { return res1; } else { return res2; } } }}Complexity
Time
O(2^(m+n)). In the worst-case scenario (when no characters match), each recursive call branches into two, leading to an exponential number of calls.
Space
O(m + n), where m and n are the lengths of the strings. This is due to the recursion depth and the storage of strings in each recursive call.
Trade-offs
Pros
Simple to understand and directly follows the problem's recursive definition.
Easy to implement without complex data structures.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs due to its exponential time complexity.
Solutions
Solution
class Solution {public String shortestCommonSupersequence(String str1, String str2) { int m = str1.length(), n = str2.length(); int[][] f = new int[m + 1][n + 1]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } } int i = m, j = n; StringBuilder ans = new StringBuilder(); while (i > 0 || j > 0) { if (i == 0) { ans.append(str2.charAt(--j)); } else if (j == 0) { ans.append(str1.charAt(--i)); } else { if (f[i][j] == f[i - 1][j]) { ans.append(str1.charAt(--i)); } else if (f[i][j] == f[i][j - 1]) { ans.append(str2.charAt(--j)); } else { ans.append(str1.charAt(--i)); --j; } } } return ans.reverse().toString(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.