| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
Medium |
1855 |
Weekly Contest 356 Q3 |
|
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
ais lexicographically smaller than a stringb(of the same length) if in the first position whereaandbdiffer, stringahas a letter that appears earlier in the alphabet than the corresponding letter inb. - 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 <= 100a,b,cconsist only of lowercase English letters.
We enumerate all permutations of the three strings, and for each permutation, we merge the three strings to find the shortest string with the smallest lexicographical order.
The time complexity is
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def f(s: str, t: str) -> str:
if s in t:
return t
if t in s:
return s
m, n = len(s), len(t)
for i in range(min(m, n), 0, -1):
if s[-i:] == t[:i]:
return s + t[i:]
return s + t
ans = ""
for a, b, c in permutations((a, b, c)):
s = f(f(a, b), c)
if ans == "" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):
ans = s
return ansclass Solution {
public String minimumString(String a, String b, String c) {
String[] s = {a, b, c};
int[][] perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
String ans = "";
for (var p : perm) {
int i = p[0], j = p[1], k = p[2];
String t = f(f(s[i], s[j]), s[k]);
if ("".equals(ans) || t.length() < ans.length()
|| (t.length() == ans.length() && t.compareTo(ans) < 0)) {
ans = t;
}
}
return ans;
}
private String f(String s, String t) {
if (s.contains(t)) {
return s;
}
if (t.contains(s)) {
return t;
}
int m = s.length(), n = t.length();
for (int i = Math.min(m, n); i > 0; --i) {
if (s.substring(m - i).equals(t.substring(0, i))) {
return s + t.substring(i);
}
}
return s + t;
}
}class Solution {
public:
string minimumString(string a, string b, string c) {
vector<string> s = {a, b, c};
vector<vector<int>> perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
string ans = "";
for (auto& p : perm) {
int i = p[0], j = p[1], k = p[2];
string t = f(f(s[i], s[j]), s[k]);
if (ans == "" || t.size() < ans.size() || (t.size() == ans.size() && t < ans)) {
ans = t;
}
}
return ans;
}
string f(string s, string t) {
if (s.find(t) != string::npos) {
return s;
}
if (t.find(s) != string::npos) {
return t;
}
int m = s.size(), n = t.size();
for (int i = min(m, n); i; --i) {
if (s.substr(m - i) == t.substr(0, i)) {
return s + t.substr(i);
}
}
return s + t;
};
};func minimumString(a string, b string, c string) string {
f := func(s, t string) string {
if strings.Contains(s, t) {
return s
}
if strings.Contains(t, s) {
return t
}
m, n := len(s), len(t)
for i := min(m, n); i > 0; i-- {
if s[m-i:] == t[:i] {
return s + t[i:]
}
}
return s + t
}
s := [3]string{a, b, c}
ans := ""
for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
i, j, k := p[0], p[1], p[2]
t := f(f(s[i], s[j]), s[k])
if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
ans = t
}
}
return ans
}function minimumString(a: string, b: string, c: string): string {
const f = (s: string, t: string): string => {
if (s.includes(t)) {
return s;
}
if (t.includes(s)) {
return t;
}
const m = s.length;
const n = t.length;
for (let i = Math.min(m, n); i > 0; --i) {
if (s.slice(-i) === t.slice(0, i)) {
return s + t.slice(i);
}
}
return s + t;
};
const s: string[] = [a, b, c];
const perm: number[][] = [
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
];
let ans = '';
for (const [i, j, k] of perm) {
const t = f(f(s[i], s[j]), s[k]);
if (ans === '' || t.length < ans.length || (t.length === ans.length && t < ans)) {
ans = t;
}
}
return ans;
}impl Solution {
fn f(s1: String, s2: String) -> String {
if s1.contains(&s2) {
return s1;
}
if s2.contains(&s1) {
return s2;
}
for i in 0..s1.len() {
let s = &s1[i..];
if s2.starts_with(s) {
let n = s.len();
return s1 + &s2[n..];
}
}
s1 + s2.as_str()
}
pub fn minimum_string(a: String, b: String, c: String) -> String {
let s = [&a, &b, &c];
let perm = [
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
];
let mut ans = String::new();
for [i, j, k] in perm.iter() {
let r = Self::f(Self::f(s[*i].clone(), s[*j].clone()), s[*k].clone());
if ans == "" || r.len() < ans.len() || (r.len() == ans.len() && r < ans) {
ans = r;
}
}
ans
}
}We can use the KMP algorithm to optimize the string merging process.
Time complexity is
class Solution:
def minimumString(self, a: str, b: str, c: str) -> str:
def f(s: str, t: str) -> str:
if s in t:
return t
if t in s:
return s
p = t + "#" + s + "$"
n = len(p)
next = [0] * n
next[0] = -1
i, j = 2, 0
while i < n:
if p[i - 1] == p[j]:
j += 1
next[i] = j
i += 1
elif j:
j = next[j]
else:
next[i] = 0
i += 1
return s + t[next[-1] :]
ans = ""
for a, b, c in permutations((a, b, c)):
s = f(f(a, b), c)
if ans == "" or len(s) < len(ans) or (len(s) == len(ans) and s < ans):
ans = s
return ansclass Solution {
public String minimumString(String a, String b, String c) {
String[] s = {a, b, c};
int[][] perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
String ans = "";
for (var p : perm) {
int i = p[0], j = p[1], k = p[2];
String t = f(f(s[i], s[j]), s[k]);
if ("".equals(ans) || t.length() < ans.length()
|| (t.length() == ans.length() && t.compareTo(ans) < 0)) {
ans = t;
}
}
return ans;
}
private String f(String s, String t) {
if (s.contains(t)) {
return s;
}
if (t.contains(s)) {
return t;
}
char[] p = (t + "#" + s + "$").toCharArray();
int n = p.length;
int[] next = new int[n];
next[0] = -1;
for (int i = 2, j = 0; i < n;) {
if (p[i - 1] == p[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s + t.substring(next[n - 1]);
}
}class Solution {
public:
string minimumString(string a, string b, string c) {
vector<string> s = {a, b, c};
vector<vector<int>> perm = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 1, 0}, {2, 0, 1}};
string ans = "";
for (auto& p : perm) {
int i = p[0], j = p[1], k = p[2];
string t = f(f(s[i], s[j]), s[k]);
if (ans == "" || t.size() < ans.size() || (t.size() == ans.size() && t < ans)) {
ans = t;
}
}
return ans;
}
string f(string s, string t) {
if (s.find(t) != string::npos) {
return s;
}
if (t.find(s) != string::npos) {
return t;
}
string p = t + "#" + s + "$";
int n = p.size();
int next[n];
next[0] = -1;
next[1] = 0;
for (int i = 2, j = 0; i < n;) {
if (p[i - 1] == p[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s + t.substr(next[n - 1]);
};
};func minimumString(a string, b string, c string) string {
f := func(s, t string) string {
if strings.Contains(s, t) {
return s
}
if strings.Contains(t, s) {
return t
}
p := t + "#" + s + "$"
n := len(p)
next := make([]int, n)
next[0] = -1
for i, j := 2, 0; i < n; {
if p[i-1] == p[j] {
j++
next[i] = j
i++
} else if j > 0 {
j = next[j]
} else {
next[i] = 0
i++
}
}
return s + t[next[n-1]:]
}
s := [3]string{a, b, c}
ans := ""
for _, p := range [][]int{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}} {
i, j, k := p[0], p[1], p[2]
t := f(f(s[i], s[j]), s[k])
if ans == "" || len(t) < len(ans) || (len(t) == len(ans) && t < ans) {
ans = t
}
}
return ans
}function minimumString(a: string, b: string, c: string): string {
const f = (s: string, t: string): string => {
if (s.includes(t)) {
return s;
}
if (t.includes(s)) {
return t;
}
const p = t + '#' + s + '$';
const n = p.length;
const next: number[] = Array(n).fill(0);
next[0] = -1;
for (let i = 2, j = 0; i < n; ) {
if (p[i - 1] === p[j]) {
next[i++] = ++j;
} else if (j) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s + t.slice(next[n - 1]);
};
const s: string[] = [a, b, c];
const perm: number[][] = [
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0],
];
let ans = '';
for (const [i, j, k] of perm) {
const t = f(f(s[i], s[j]), s[k]);
if (ans === '' || t.length < ans.length || (t.length === ans.length && t < ans)) {
ans = t;
}
}
return ans;
}