Skip to content

555. Split Concatenated Strings 👎

  • Time: $\Sigma(n \cdot |\texttt{strs[i]}| \cdot \Sigma |\texttt{strs[i]}|)$
  • Space: $\Sigma |\texttt{strs[i]}|$
 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 {
 public:
  string splitLoopedString(vector<string>& strs) {
    string ans;
    vector<string> sortedStrs;

    for (const string& s : strs)
      sortedStrs.push_back(max(s, {s.rbegin(), s.rend()}));

    for (int i = 0; i < sortedStrs.size(); ++i)
      for (const string& s :
           {sortedStrs[i], {sortedStrs[i].rbegin(), sortedStrs[i].rend()}})
        for (int j = 0; j <= s.length(); ++j)
          ans = max(ans, s.substr(j) + join(sortedStrs, i) + s.substr(0, j));

    return ans;
  }

 private:
  string reversed(const string& s) {
    return {s.rbegin(), s.rend()};
  }

  string join(const vector<string>& sortedStrs, int i) {
    string joined;
    for (int j = i + 1; j < sortedStrs.size(); ++j)
      joined += sortedStrs[j];
    for (int j = 0; j < i; ++j)
      joined += sortedStrs[j];
    return joined;
  }
};

 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 {
  public String splitLoopedString(String[] strs) {
    String ans = "";
    String[] sortedStrs = new String[strs.length];

    for (int i = 0; i < strs.length; ++i) {
      final String s = strs[i];
      final String r = new StringBuilder(s).reverse().toString();
      sortedStrs[i] = s.compareTo(r) > 0 ? s : r;
    }

    for (int i = 0; i < sortedStrs.length; ++i)
      for (final String s :
           new String[] {sortedStrs[i], new StringBuilder(sortedStrs[i]).reverse().toString()})
        for (int j = 0; j <= s.length(); ++j) {
          final String t = s.substring(j) + join(sortedStrs, i) + s.substring(0, j);
          if (t.compareTo(ans) > 0)
            ans = t;
        }

    return ans;
  }

  private String join(String[] sortedStrs, int i) {
    StringBuilder sb = new StringBuilder();
    for (int j = i + 1; j < sortedStrs.length; ++j)
      sb.append(sortedStrs[j]);
    for (int j = 0; j < i; ++j)
      sb.append(sortedStrs[j]);
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def splitLoopedString(self, strs: list[str]) -> str:
    ans = ''
    sortedStrs = [max(s, s[::-1]) for s in strs]

    for i, sortedStr in enumerate(sortedStrs):
      for s in (sortedStr, sortedStr[::-1]):
        for j in range(len(s) + 1):
          ans = max(
              ans, s[j:] + ''.join(sortedStrs[i + 1:] + sortedStrs[:i]) + s[:j])

    return ans