## Split Concatenated Strings

• Time:\Sigma(n \cdot |\texttt{strs[i]}| \cdot \Sigma |\texttt{strs[i]}|)
• Space:\Sigma |\texttt{strs[i]}|

## C++

class Solution {
public:
string splitLoopedString(vector<string>& strs) {
string ans;
vector<string> sortedStrs;

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

for (int i = 0; i < sortedStrs.size(); ++i)
for (const auto& 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<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;
}
};


## JAVA

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();
}
}


## Python

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