Skip to content

2800. Shortest String That Contains Three Strings

  • Time: $O(|\texttt{a}||\texttt{b}| + |\texttt{a}||\texttt{c}| + |\texttt{b}||\texttt{c}|)$
  • Space: $O(|\texttt{a}| + |\texttt{b}| + |\texttt{c}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public 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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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