2800. Shortest String That Contains Three Strings LeetCode Solution
In this guide, you will get 2800. Shortest String That Contains Three Strings LeetCode Solution with the best time and space complexity. The solution to Shortest String That Contains Three Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Shortest String That Contains Three Strings solution in C++
- Shortest String That Contains Three Strings solution in Java
- Shortest String That Contains Three Strings solution in Python
- Additional Resources
Problem Statement of Shortest String That Contains Three Strings
Given three strings a, b, and c, your task is to find a string that has the minimum length and contains all three strings as substrings.
If there are multiple such strings, return the lexicographically smallest one.
Return a string denoting the answer to the problem.
Notes
A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: a = “abc”, b = “bca”, c = “aaa”
Output: “aaabca”
Explanation: We show that “aaabca” contains all the given strings: a = ans[2…4], b = ans[3..5], c = ans[0..2]. It can be shown that the length of the resulting string would be at least 6 and “aaabca” is the lexicographically smallest one.
Example 2:
Input: a = “ab”, b = “ba”, c = “aba”
Output: “aba”
Explanation: We show that the string “aba” contains all the given strings: a = ans[0..1], b = ans[1..2], c = ans[0..2]. Since the length of c is 3, the length of the resulting string would be at least 3. It can be shown that “aba” is the lexicographically smallest one.
Constraints:
1 <= a.length, b.length, c.length <= 100
a, b, c consist only of lowercase English letters.
Complexity Analysis
- Time Complexity: O(|\texttt{a}||\texttt{b}| + |\texttt{a}||\texttt{c}| + |\texttt{b}||\texttt{c}|)
- Space Complexity: O(|\texttt{a}| + |\texttt{b}| + |\texttt{c}|)
2800. Shortest String That Contains Three Strings LeetCode Solution in C++
class Solution {
public:
string minimumString(string a, string b, string c) {
const string abc = merge(a, merge(b, c));
const string acb = merge(a, merge(c, b));
const string bac = merge(b, merge(a, c));
const string bca = merge(b, merge(c, a));
const string cab = merge(c, merge(a, b));
const string cba = merge(c, merge(b, a));
return getMin({abc, acb, bac, bca, cab, cba});
}
private:
// Merges a and b.
string merge(const string& a, const string& b) {
if (b.find(a) != string::npos) // a is a substring of b.
return b;
for (int i = 0; i < a.length(); ++i) {
const string aSuffix = a.substr(i);
const string bPrefix = b.substr(0, min(b.length(), aSuffix.length()));
if (aSuffix == bPrefix)
return a + b.substr(bPrefix.length());
}
return a + b;
}
// Returns the lexicographically smallest string.
string getMin(const vector<string>& words) {
string res = words[0];
for (int i = 1; i < words.size(); ++i)
res = getMin(res, words[i]);
return res;
}
// Returns the lexicographically smaller string.
string getMin(const string& a, const string& b) {
return (a.length() < b.length() || (a.length() == b.length() && a < b)) ? a
: b;
}
};
/* code provided by PROGIEZ */2800. Shortest String That Contains Three Strings LeetCode Solution in Java
class Solution {
public String minimumString(String a, String b, String c) {
final String abc = merge(a, merge(b, c));
final String acb = merge(a, merge(c, b));
final String bac = merge(b, merge(a, c));
final String bca = merge(b, merge(c, a));
final String cab = merge(c, merge(a, b));
final String cba = merge(c, merge(b, a));
return getMin(Arrays.asList(abc, acb, bac, bca, cab, cba));
}
// Merges a and b.
private String merge(String a, String b) {
if (b.contains(a)) // a is a substring of b.
return b;
for (int i = 0; i < a.length(); ++i) {
final String aSuffix = a.substring(i);
final String bPrefix = b.substring(0, Math.min(b.length(), aSuffix.length()));
if (aSuffix.equals(bPrefix))
return a + b.substring(bPrefix.length());
}
return a + b;
}
// Returns the lexicographically smallest string.
private String getMin(List<String> words) {
String res = words.get(0);
for (int i = 1; i < words.size(); ++i)
res = getMin(res, words.get(i));
return res;
}
// Returns the lexicographically smaller string.
private String getMin(String a, String b) {
return (a.length() < b.length() || (a.length() == b.length() && a.compareTo(b) < 0)) ? a : b;
}
}
// code provided by PROGIEZ2800. Shortest String That Contains Three Strings LeetCode Solution in Python
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def merge(a: str, b: str) -> str:
"""Merges a and b."""
if a in b: # a is a substring of b.
return b
for i in range(len(a)):
aSuffix = a[i:]
bPrefix = b[:len(aSuffix)]
if aSuffix == bPrefix:
return a + b[len(bPrefix):]
return a + b
abc = merge(a, merge(b, c))
acb = merge(a, merge(c, b))
bac = merge(b, merge(a, c))
bca = merge(b, merge(c, a))
cab = merge(c, merge(a, b))
cba = merge(c, merge(b, a))
return self._getMin([abc, acb, bac, bca, cab, cba])
def _getMin(self, words: list[str]) -> str:
"""Returns the lexicographically smallest string."""
def getMin(a: str, b: str) -> str:
"""Returns the lexicographically smaller string."""
return a if len(a) < len(b) or (len(a) == len(b) and a < b) else b
res = words[0]
for i in range(1, len(words)):
res = getMin(res, words[i])
return res
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.