Question

2800. Shortest String That Contains Three Strings

中文文档

Description

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.

Solutions

Solution 1: Enumeration

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 $O(n^2)$, and the space complexity is $O(n)$. Where $n$ is the maximum length of the three strings.

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 ans

class 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
  }
}