# LeetCode 555: Split Concatenated Strings

## Problem Restatement

We are given an array of strings `strs`.

We can concatenate the strings into a loop. For each string, we may use it normally or reversed. The strings must stay in the same order as given.

After forming the loop, we choose one cut point. Cutting the loop turns it into a normal string.

Our goal is to return the lexicographically largest possible string.

The input strings contain only lowercase letters, and the total length of all strings is at most `1000`. The problem statement describes the process as two phases: concatenate the strings into a loop with optional reversals, then cut the loop at one breakpoint.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of strings `strs` |
| Output | The lexicographically largest regular string after forming and cutting a loop |
| Allowed | Reverse any individual string before concatenation |
| Required | Keep strings in the same order |
| Cut | Can happen at any character position in the loop |

Example function shape:

```python
def splitLoopedString(strs: list[str]) -> str:
    ...
```

## Examples

Example:

```python
strs = ["abc", "xyz"]
```

For each string, we can choose the original or reversed form.

So possible loop forms include:

```python
"abcxyz"
"abczyx"
"cbaxyz"
"cbazyx"
```

The best result comes from the loop:

```python
"cbazyx"
```

If we cut so that the result starts at the `"z"` in `"zyx"`, we get:

```python
"zyxcba"
```

So the answer is:

```python
"zyxcba"
```

## First Thought: Try Every Reversal Combination

A direct solution is to try every possible choice of reversing or not reversing each string.

If there are `n` strings, each string has two choices:

```python
2 ** n
```

After choosing the orientation of every string, we can concatenate them into a loop and try every cut point.

This works logically, but it repeats too much work. We need a sharper way to reduce the choices.

## Key Insight

Only one string is split by the final cut.

All other strings remain whole.

Suppose the cut happens inside `strs[i]`.

Then every other string is not split. For those other strings, we should simply choose the lexicographically larger version between the original and reversed form.

That is:

```python
max(s, s[::-1])
```

The only string that still needs special handling is the cut string. For that string, we must try both orientations and every possible cut position.

So the algorithm is:

1. Preprocess every string into its better orientation.
2. For each string `i`, treat it as the string containing the cut.
3. Try every cut position inside that string.
4. Try both the original and reversed orientation for that cut string.
5. Keep the lexicographically largest candidate.

This avoids trying all `2 ** n` global reversal combinations.

## Why Other Strings Can Be Optimized Independently

If a string is not cut, it appears as one whole block in the final answer.

Its only choice is:

```python
s
```

or:

```python
s[::-1]
```

Nothing else changes inside that block.

So for every uncut string, using the larger of the two versions can only improve the final candidate lexicographically, or leave it unchanged.

The cut string is different because it is split into a suffix at the beginning and a prefix at the end. Its best orientation depends on the cut position, so we cannot fix it once in preprocessing.

## Algorithm

First, replace every string with its better orientation:

```python
best = [max(s, s[::-1]) for s in strs]
```

Then enumerate the cut string.

For each index `i`:

1. Build the middle part using all other already-optimized strings:
   ```python id="4kfpgy"
   middle = "".join(best[i + 1:]) + "".join(best[:i])
   ```

2. Try both orientations of the current string:
   ```python id="qej5ib"
   for cur in (strs[i], strs[i][::-1]):
   ```

3. Try every cut position `j`:
   ```python id="aa3a86"
   candidate = cur[j:] + middle + cur[:j]
   ```

4. Keep the largest candidate.

## Correctness

Consider an optimal final answer.

The final cut occurs inside exactly one string, say `strs[i]`. This string may be used in its original form or reversed form, and the cut may happen at any position inside that chosen orientation.

All other strings are not split. Since they remain whole blocks, each one can only appear as either `s` or `s[::-1]`. Choosing the lexicographically larger of those two forms is always at least as good for the final string as choosing the smaller form, because the block appears unchanged as a contiguous part of the candidate.

The algorithm tries every possible choice of the cut string `i`. For that string, it tries both orientations and every cut position. For all other strings, it uses their best whole-block orientation.

Therefore, the algorithm constructs the optimal candidate among all valid loop formations and cut points. Since it returns the maximum candidate seen, it returns the lexicographically largest possible string.

## Complexity

Let `L` be the total length of all strings.

| Metric | Value | Why |
|---|---|---|
| Time | `O(L^2)` | For each possible cut position, we build a candidate string of length `L` |
| Space | `O(L)` | We store optimized strings and candidate strings |

The total number of cut positions across all strings is `L`. Each candidate has length `L`, so the overall time is `O(L^2)`.

## Implementation

```python
class Solution:
    def splitLoopedString(self, strs: list[str]) -> str:
        best = [max(s, s[::-1]) for s in strs]
        ans = ""

        for i, original in enumerate(strs):
            middle = "".join(best[i + 1:]) + "".join(best[:i])

            for cur in (original, original[::-1]):
                for j in range(len(cur)):
                    candidate = cur[j:] + middle + cur[:j]
                    if candidate > ans:
                        ans = candidate

        return ans
```

## Code Explanation

We first choose the better whole-block orientation for every string:

```python
best = [max(s, s[::-1]) for s in strs]
```

This is safe for strings that are not cut.

Then we enumerate each string as the possible cut string:

```python
for i, original in enumerate(strs):
```

The middle part contains every other string in loop order, starting after `i` and wrapping around:

```python
middle = "".join(best[i + 1:]) + "".join(best[:i])
```

Then we try both orientations of the cut string:

```python
for cur in (original, original[::-1]):
```

For each orientation, we try every cut position:

```python
candidate = cur[j:] + middle + cur[:j]
```

The suffix `cur[j:]` becomes the beginning of the final string.

The prefix `cur[:j]` moves to the end.

We update the answer whenever we find a lexicographically larger candidate.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.splitLoopedString(["abc", "xyz"]) == "zyxcba"
    assert s.splitLoopedString(["abc"]) == "cba"
    assert s.splitLoopedString(["aaa"]) == "aaa"
    assert s.splitLoopedString(["ab", "cd"]) == "dcba"
    assert s.splitLoopedString(["lc", "evol", "cdy"]) == "ylclovecd"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `["abc", "xyz"]` | Official-style sample |
| `["abc"]` | Single string, best rotation of original or reversed |
| `["aaa"]` | All candidates equal |
| `["ab", "cd"]` | Checks reversal and loop cut behavior |
| `["lc", "evol", "cdy"]` | Checks several strings with different reversal choices |