Leetcode 2800: Shortest String That Contains Three Strings
Given three strings ‘a’, ‘b’, and ‘c’, find a string that contains all three of these strings as substrings and has the minimum possible length. If there are multiple such strings, return the lexicographically smallest one.
Problem
Approach
Steps
Complexity
Input: You are given three strings, 'a', 'b', and 'c'. Each string consists of lowercase English letters.
Example: Input: a = 'apple', b = 'banana', c = 'orange'
Constraints:
• 1 <= a.length, b.length, c.length <= 100
• a, b, c consist only of lowercase English letters.
Output: Return a string that contains all three strings 'a', 'b', and 'c' as substrings and has the minimum length. If there are multiple valid answers, return the lexicographically smallest one.
Example: Output: 'bananaorange'
Constraints:
Goal: Find the shortest string that contains all three given strings as substrings.
Steps:
• 1. Identify the possible overlapping parts of the strings to minimize the total length.
• 2. Try all permutations of the strings to find the lexicographically smallest solution.
• 3. Combine the strings efficiently using the overlap method and return the result.
Goal: The strings a, b, and c will have lengths ranging from 1 to 100, and will consist of lowercase English letters.
Steps:
• 1 <= a.length, b.length, c.length <= 100
• a, b, c consist only of lowercase English letters.
Assumptions:
• The input strings are non-empty and consist only of lowercase English letters.
• Input: Input: a = 'apple', b = 'banana', c = 'orange'
• Explanation: The lexicographically smallest string that contains all three strings as substrings is 'bananaorange'.
• Input: Input: a = 'cat', b = 'bat', c = 'rat'
• Explanation: The shortest and lexicographically smallest string that contains all three strings as substrings is 'catbat'.
Approach: The problem can be solved by finding the minimal overlap between each pair of strings and combining them efficiently.
Observations:
• Finding the minimal overlap between strings will allow us to reduce the length of the combined string.
• We need to explore permutations of the three strings to ensure we get the lexicographically smallest result.
Steps:
• Step 1: Implement a helper function to find the overlap between two strings.
• Step 2: Use this function to combine each pair of strings with the minimum overlap.
• Step 3: Try all permutations of the three strings and choose the lexicographically smallest result.
Empty Inputs:
• The input strings will never be empty based on the problem constraints.
Large Inputs:
• The algorithm should be optimized to handle strings up to 100 characters long.
Special Values:
• If all strings are identical, the output will be the same string.
Constraints:
• The solution must handle strings of length up to 100 efficiently.
string mn(string a, string b) {
return (a.size() < b.size() || (a.size() == b.size() && a < b))? a: b;
}
string attach(string a, string b) {
if(a.find(b) != string::npos) return a;
for(int i = 0; i < a.size(); i++) {
string t1 = a.substr(i), t2 = b.substr(0, t1.size());
if(t1 == t2) return a + b.substr(t1.size());
}
return a + b;
}
string solve(string a, string b, string c) {
string t1 = attach(a, b);
string t2 = attach(b, a);
string ret1 = attach(t1, c);
string ret2 = attach(c, t1);
string ret3 = attach(t2, c);
string ret4 = attach(c, t2);
return mn(mn(ret1, ret2), mn(ret3, ret4));
}
string minimumString(string a, string b, string c) {
return mn(mn(solve(a, b, c), solve(a, c, b)), solve(b, c, a));
}
1 : Initialization
This section initializes the necessary functions that will be used to solve the problem.
2 : Define Mn Function
string mn(string a, string b) {
The `mn` function returns the lexicographically smaller of two strings. It compares the sizes of the strings and, if they are equal, compares them lexicographically.
3 : Mn Comparison Logic
return (a.size() < b.size() || (a.size() == b.size() && a < b))? a: b;
This line performs the comparison between the two strings `a` and `b`. It first checks their lengths and, if they are equal, it checks which string is lexicographically smaller.
4 : Define Attach Function
string attach(string a, string b) {
The `attach` function concatenates two strings, ensuring that no duplicate parts are added if they already match.
5 : Attach Function Logic
if(a.find(b) != string::npos) return a;
If string `b` is already a part of string `a`, the function directly returns `a` without modification.
6 : Attach Loop
for(int i = 0; i < a.size(); i++) {
This loop checks the various substrings of `a` to find a match with the beginning of `b`.
7 : Attach Substring Check
string t1 = a.substr(i), t2 = b.substr(0, t1.size());
For each substring of `a`, it compares it with the beginning part of `b`.
8 : Attach Match Found
if(t1 == t2) return a + b.substr(t1.size());
If a matching substring is found, the function returns `a` with the remaining part of `b` concatenated to it.
9 : Attach Return
return a + b;
If no matching substring was found, the function simply concatenates `a` and `b`.
10 : Define Solve Function
string solve(string a, string b, string c) {
The `solve` function takes three strings and combines them using the `attach` function to generate possible combinations.
11 : Solve Function Attachments
string t1 = attach(a, b);
The first combination of `a` and `b` is created and stored in `t1`.
12 : Solve Function Reverse Attachment
string t2 = attach(b, a);
The second combination of `b` and `a` is created and stored in `t2`.
13 : Solve Function Further Attachments
string ret1 = attach(t1, c);
The result of combining `t1` with `c` is stored in `ret1`.
14 : Solve Function More Attachments
string ret2 = attach(c, t1);
The result of combining `c` with `t1` is stored in `ret2`.
15 : Solve Function Attach Remaining
string ret3 = attach(t2, c);
The result of combining `t2` with `c` is stored in `ret3`.
16 : Solve Function Final Attachment
string ret4 = attach(c, t2);
The result of combining `c` with `t2` is stored in `ret4`.
17 : Solve Function Return
return mn(mn(ret1, ret2), mn(ret3, ret4));
The function returns the smallest of the four possible combinations using the `mn` function.
18 : Define MinimumString Function
string minimumString(string a, string b, string c) {
The `minimumString` function computes the minimum string formed by all possible combinations of the input strings `a`, `b`, and `c`.
19 : MinimumString Logic
return mn(mn(solve(a, b, c), solve(a, c, b)), solve(b, c, a));
The function returns the smallest string from all the combinations generated by calling the `solve` function with different orderings of `a`, `b`, and `c`.
Best Case: O(n!)
Average Case: O(n!)
Worst Case: O(n!)
Description: The time complexity is dominated by the permutations of the three strings (3! = 6 permutations). For each permutation, the overlap checking requires linear time, so the overall complexity is O(6n), which simplifies to O(n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we only store the intermediate results of string combinations.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus