# 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 33 34 class Solution { public: string splitLoopedString(vector& strs) { string ans; vector sortedStrs; for (const string& s : strs) sortedStrs.push_back(max(s, {rbegin(s), rend(s)})); for (int i = 0; i < sortedStrs.size(); ++i) for (const string& s : {sortedStrs[i], {rbegin(sortedStrs[i]), rend(sortedStrs[i])}}) 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) { string r = s; reverse(begin(r), end(r)); return r; } string join(const vector& 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