Problem statement

https://leetcode.com/problems/split-concatenated-strings/

Solution

We can note, that if some string string in strs is not cut in two parts, than it is always more profitable to choose maximum of string, string[::-1]. However there can be one string, which is cut in the middle. So, let us first create long string s with all parts max(string, string[::-1]). Then we traverse through all n strings and for each possible cut and direction build candidate and compare it with res.

Complexity

Time complexity is O(m^2), where m is total length of all strings and space complexity is O(m).

Code

class Solution:
    def splitLoopedString(self, strs):
        if not strs: return ""
        s, res = "", ""
        n, cur = len(strs), 0
        for string in strs:
            s += max(string, string[::-1])
            
        for i in range(n):
            t1, t2 = strs[i], strs[i][::-1]
            m = len(t1)
            mid = s[cur + m:] + s[:cur]
            for j in range(m):
                res = max(res, t1[j:] + mid + t1[:j])
                res = max(res, t2[j:] + mid + t2[:j])
                
            cur += m
            
        return res