## 555. Split Concatenated Strings

Given a list of strings, you could concatenate these strings together into a loop, where for each string you could choose to reverse it or not. Among all the possible loops, you need to find the lexicographically biggest string after cutting the loop, which will make the looped string into a regular one.

Specifically, to find the lexicographically biggest string, you need to experience two phases:

1. Concatenate all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
2. Cut and make one breakpoint in any place of the loop, which will make the looped string into a regular one starting from the character at the cutpoint.

And your job is to find the lexicographically biggest one among all the possible regular strings.

Example:

Input: "abc", "xyz"
Output: "zyxcba"
Explanation: You can get the looped string "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-",
where '-' represents the looped status.
The answer string came from the fourth looped one,
where you could cut from the middle character 'a' and get "zyxcba".

Note:

1. The input strings will only contain lowercase letters.
2. The total length of all the strings will not over 1,000.

b'
\n\n

## Summary

\n

We are given a list of strings: . We need to concatenate all these strings in a circular fashion in the same given order, but we can reverse every individual string before concatenating. Now, we need to make a cut in the final concatenated string such that the new string formed is the largest one possible in the lexicographic sense

\n

## Solution

\n
\n

#### Approach #1 Depth First Search [Time Limit Exceeded]

\n

The simplest solution is to try forming every possible concatenated string by making use of the given strings and then forming every possible cut in each such final concatenated string.

\n

To do so, we can make use of a recursive function dfs which appends the current string to the concatenated string formed till now and calls itself with the new concatenated string. It also appends the reversed current string to the current concatenated string and calls itself. The concatenation of strings goes in the manner of a Depth First Search.\nThus, after reaching the full depth of every branch traversal, we obtain a new concatenated string as illustrated in the animation below. We can apply all the possible cuts to these strings and find the lexicographically largest string out of all of them.

\n

!?!../Documents/555_Split_Assembled_Strings.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• Time complexity : . Size of Recursion tree can grow upto where is the number of strings in the list.
• \n
• Space complexity : . Depth of Recursion tree will be \n
• \n
\n
\n

#### Approach #2 Breadth First Search [Memory Limit Exceeded]

\n

Algorithm

\n

Exploring all strings can also be done using BFS method. A Queue is maintained which stores the strings formed till now after concatenation of the next string and also by concatenation of reverse of next string. Every time we remove a string from the front of the queue, we add two strings to the back of the queue(one by concatenating the next string directly and another by concatenating the next string after reversing).

\n

When all the strings are traversed queue contains strings, which correspond to every possible valid string which can be formed by doing the concatenations. We check every string into the queue after circularly rotating by placing the cuts at every possible location. While doing this, we keep a track of the lexicographically largest string.

\n

This animation will depict the method:

\n

!?!../Documents/555_Split_Assembled_Strings1.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . possible strings will be formed where is the number of strings in the list.

\n
• \n
• \n

Space complexity : . \'s size can grow upto .

\n
• \n
\n
\n

#### Approach #3 Optimized Solution [Accepted]

\n

Algorithm

\n

In order to understand how this solution works, firstly we\'ll look at some of the properties of the transformation involved. The first point to note is that the relative ordering of the strings doesn\'t change after applying the transformations(i.e. reversing and applying cuts).

\n

The second property will be explained taking the help of an example. Consider the given list of strings: . Now, assume that we choose to be the string on which the current cut is placed leading to the formation of two substrings from , namely, say , . Thus, the concatenated string formed by such a cut will be: . Here, means the reversed string.

\n

The concatenated string formed follows the same pattern irrespective of where the cut is placed in . But still, the relative ordering of the strings persists, even if we include the reverse operation as well.

\n

Now, if we consider only a single cut for the time being, in string (not reversed) as discussed above, and allow for the reverse operation among the remaining strings, the lexicographically largest concatenated string will be given by: . Here, refers to the lexicographic maximum operation.

\n

Thus, if a particular string is finalized for the cut, the largest lexicographic concatenated string is dependent only on whether the string is reversed or not, and also on the position of the cut. This happens because the reverse/not reverse operation for the rest of the strings is fixed for a chosen as shown above and thus, doesn\'t impact the final result.

\n

Based on the above observations, we follow the given procedure. For every given string, we replace the string with the lexicographically larger string out of the original string and the reversed one. After this, we pick up every new string(chosen as the string on which the cuts will be applied), and apply a cut at all the positions of the currently picked string and form the full concantenated string keeping the rest of the newly formed strings intact. We also reverse the current string and follow the same process. While doing this, we keep a track of the largest lexicographic string found so far.

\n

For a better understanding of the procedure, watch this animation:

\n

!?!../Documents/555_Split_Assembled_Strings2.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . where is the total number of characters in a list.

\n
• \n
• \n

Space complexity : . and of size are used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'