LeetCode 555 - Split Concatenated Strings
The problem gives an array of strings, and we must arrange them into a circular concatenation while preserving the original order of the strings. For every individual string, we are allowed to either keep it as-is or reverse it before joining it into the loop.
Difficulty: 🟡 Medium
Topics: Array, String, Greedy
Solution
Problem Understanding
The problem gives an array of strings, and we must arrange them into a circular concatenation while preserving the original order of the strings. For every individual string, we are allowed to either keep it as-is or reverse it before joining it into the loop.
After constructing this circular string, we may cut the loop at any position to transform it into a normal linear string. Among every possible configuration, we must return the lexicographically largest resulting string.
The important detail is that there are two independent choices:
- For each string, choose either the original version or the reversed version.
- Choose a cut position somewhere in the circular concatenation.
The output is the largest lexicographical string obtainable after making both choices optimally.
For example, suppose we have:
["abc", "xyz"]
We may reverse either string:
abc or cba
xyz or zyx
One valid loop is:
cbazyx
Because the string is circular, we may cut it anywhere. Cutting before 'z' gives:
zyxcba
which turns out to be the largest possible answer.
The constraints are extremely important:
- At most 1000 strings
- Total combined length of all strings is at most 1000
This means the total amount of data is relatively small. An algorithm with quadratic complexity in the total character count is acceptable. However, generating every possible combination of reversals would still be too expensive because there are 2^n reversal configurations.
Several edge cases are important:
- A single string input, where the answer is simply the better of the string and its reverse.
- Strings whose reverse is lexicographically identical, such as
"aaa". - Cases where the optimal cut occurs in the middle of a string rather than at a boundary.
- Cases where reversing a locally smaller string creates a globally larger result after rotation.
Approaches
Brute Force Approach
The brute-force solution tries every possible reversal configuration.
For n strings, each string has two choices:
- original
- reversed
This creates 2^n total combinations.
For every combination:
- Construct the looped string.
- Try every possible cut position.
- Generate the resulting linear string.
- Keep the lexicographically largest answer.
This approach is correct because it explicitly enumerates every valid configuration and every possible cut.
However, it is far too slow. Even with only 1000 strings, 2^1000 configurations are impossible to enumerate.
Key Insight
The crucial observation is that for each string, we only ever want the lexicographically larger version between:
- the original string
- its reverse
Why?
Suppose a string contributes to parts of the final answer that are not at the starting position. In lexicographical comparison, earlier characters dominate later characters. Therefore, for all non-starting strings, choosing the lexicographically larger orientation is always optimal.
The only string that needs special handling is the one containing the cut position, because the answer may begin in the middle of that string.
So the strategy becomes:
- Preprocess every string into its lexicographically larger orientation.
- For each string:
- Treat it as the starting string.
- Try both orientations of that string.
- Try every cut position inside it.
- Construct the candidate answer and update the best result.
This reduces the search dramatically.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n × L^2) | O(L) | Enumerates every reversal combination and every cut |
| Optimal | O(L^2) | O(L) | Uses greedy orientation selection and checks all rotations |
Here, L is the total number of characters across all strings.
Algorithm Walkthrough
Step 1: Normalize Every String
For every string in the array:
- Compute its reverse.
- Keep whichever is lexicographically larger.
For example:
"abc" -> "cba"
"xyz" -> "zyx"
This works because any string not containing the cut should contribute its best possible ordering.
Step 2: Iterate Over Every Possible Starting String
Each string may contain the cut position.
Suppose index i is chosen as the starting string.
We must consider both:
- the normalized version
- the reverse version
because the optimal cut may require either orientation.
Step 3: Try Every Cut Position Inside the Current String
If the current candidate string is:
current
then every position k inside current may become the beginning of the final answer.
The resulting string becomes:
current[k:] +
remaining_strings +
current[:k]
where remaining_strings are appended in circular order.
Step 4: Build the Candidate String
The candidate is constructed as:
- Suffix of the current string after the cut.
- All subsequent normalized strings.
- All previous normalized strings.
- Prefix of the current string before the cut.
This simulates cutting the circular loop at position k.
Step 5: Update the Best Answer
Compare the generated candidate with the current best answer.
If the candidate is lexicographically larger, update the answer.
Why it works
The key invariant is that every string except the one containing the cut should always use its lexicographically maximum orientation. Any smaller orientation would only worsen characters appearing later in the final result.
The only uncertainty comes from the string where the cut occurs, because the answer begins inside it. By exhaustively trying every position and both orientations of that string, the algorithm explores every meaningful candidate while avoiding the exponential explosion of reversal combinations.
Python Solution
from typing import List
class Solution:
def splitLoopedString(self, strs: List[str]) -> str:
# Normalize each string to its lexicographically larger form
normalized = [max(s, s[::-1]) for s in strs]
best = ""
for i, original in enumerate(strs):
# Try both orientations for the current string
for current in [original, original[::-1]]:
for cut in range(len(current)):
candidate = []
# Start from the cut position
candidate.append(current[cut:])
# Add strings after current
for j in range(i + 1, len(strs)):
candidate.append(normalized[j])
# Add strings before current
for j in range(i):
candidate.append(normalized[j])
# Add remaining prefix of current
candidate.append(current[:cut])
candidate_string = "".join(candidate)
if candidate_string > best:
best = candidate_string
return best
The implementation begins by preprocessing every string into its lexicographically larger orientation. This step drastically reduces the search space because all non-starting strings should always contribute their maximum possible value.
The outer loop chooses which string contains the cut position. For that string, the algorithm explicitly checks both the original and reversed orientations because the cut may change which orientation is optimal.
The inner loop iterates through every possible cut index inside the current string. For each cut:
- The suffix after the cut becomes the beginning.
- All remaining normalized strings are appended in circular order.
- The prefix before the cut is appended at the end.
Each constructed candidate is compared lexicographically against the best answer found so far.
Because the total input length is at most 1000, constructing these candidate strings directly is efficient enough.
Go Solution
package main
func splitLoopedString(strs []string) string {
normalized := make([]string, len(strs))
for i, s := range strs {
rev := reverse(s)
if rev > s {
normalized[i] = rev
} else {
normalized[i] = s
}
}
best := ""
for i, s := range strs {
candidates := []string{s, reverse(s)}
for _, current := range candidates {
for cut := 0; cut < len(current); cut++ {
candidate := current[cut:]
for j := i + 1; j < len(strs); j++ {
candidate += normalized[j]
}
for j := 0; j < i; j++ {
candidate += normalized[j]
}
candidate += current[:cut]
if candidate > best {
best = candidate
}
}
}
}
return best
}
func reverse(s string) string {
chars := []byte(s)
left := 0
right := len(chars) - 1
for left < right {
chars[left], chars[right] = chars[right], chars[left]
left++
right--
}
return string(chars)
}
The Go implementation follows the exact same algorithmic structure as the Python version. The primary difference is manual string reversal using a byte slice.
Go strings are immutable, so reversing requires converting the string into a mutable byte slice, swapping characters in place, and converting back to a string.
Since the problem guarantees lowercase English letters only, byte-based reversal is completely safe.
Worked Examples
Example 1
Input:
["abc", "xyz"]
Step 1: Normalize Strings
| Original | Reverse | Chosen |
|---|---|---|
| abc | cba | cba |
| xyz | zyx | zyx |
Normalized array:
["cba", "zyx"]
Step 2: Try First String as Starting String
Current string:
abc
Try cuts:
| Cut | Candidate |
|---|---|
| 0 | abczyx |
| 1 | bczyxa |
| 2 | czyxab |
Now try reversed version:
cba
| Cut | Candidate |
|---|---|
| 0 | cbazyx |
| 1 | bazyxc |
| 2 | azyxcb |
Current best:
czyxab
Step 3: Try Second String as Starting String
Current string:
xyz
| Cut | Candidate |
|---|---|
| 0 | xyzcba |
| 1 | yzc bax |
| 2 | zcbaxy |
Now reversed:
zyx
| Cut | Candidate |
|---|---|
| 0 | zyxcba |
| 1 | yxcbaz |
| 2 | cbazyx |
Largest result:
zyxcba
Example 2
Input:
["abc"]
Normalized:
["cba"]
Try original:
| Cut | Candidate |
|---|---|
| 0 | abc |
| 1 | bca |
| 2 | cab |
Try reversed:
| Cut | Candidate |
|---|---|
| 0 | cba |
| 1 | bac |
| 2 | acb |
Largest result:
cba
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(L^2) | Every character position may generate a candidate string of length L |
| Space | O(L) | Temporary candidate construction |
Let L be the total number of characters across all strings.
The algorithm examines every possible cut position across all strings. Since there are L total positions and each candidate construction may take O(L) time, the total complexity becomes O(L^2).
Because L ≤ 1000, this is easily fast enough.
Test Cases
sol = Solution()
# Provided examples
assert sol.splitLoopedString(["abc", "xyz"]) == "zyxcba" # example 1
assert sol.splitLoopedString(["abc"]) == "cba" # single string
# Single character
assert sol.splitLoopedString(["a"]) == "a" # smallest possible input
# Palindrome string
assert sol.splitLoopedString(["aba"]) == "baa" # reverse is identical
# Multiple identical strings
assert sol.splitLoopedString(["aaa", "aaa"]) == "aaaaaa" # all equal
# Reverse improves lexicographical order
assert sol.splitLoopedString(["az", "by"]) == "zyxba" # reversal matters
# Optimal cut inside a string
assert sol.splitLoopedString(["abc", "def"]) == "fedcba" # cut not at boundary
# Larger mixed example
assert sol.splitLoopedString(["abc", "xyz", "pqr"]) == "zyxrqpabc"
# Strings already optimal
assert sol.splitLoopedString(["zyx", "wvu"]) == "zyxwvu"
# Edge case with repeated characters
assert sol.splitLoopedString(["bbbb", "aa"]) == "bbbbaa"
# Complex rotation behavior
assert sol.splitLoopedString(["cac", "b"]) == "ccab"
Test Summary
| Test | Why |
|---|---|
["abc", "xyz"] |
Validates the main example |
["abc"] |
Tests single-string handling |
["a"] |
Smallest possible input |
["aba"] |
Handles palindrome strings |
["aaa", "aaa"] |
All rotations identical |
["az", "by"] |
Ensures reversal optimization works |
["abc", "def"] |
Verifies cuts inside strings |
["abc", "xyz", "pqr"] |
Tests multiple-string circular ordering |
["zyx", "wvu"] |
Already maximal orientations |
["bbbb", "aa"] |
Repeated-character edge case |
["cac", "b"] |
Nontrivial lexicographical comparison |
Edge Cases
Single String Input
When only one string exists, the loop consists entirely of that string. The algorithm must still consider both orientations and every cut position. A buggy implementation might simply return the lexicographically larger between the string and its reverse, but the best answer may come from a rotation after cutting.
The implementation correctly handles this because it still iterates through every cut position.
Optimal Cut Occurs Inside a String
A common mistake is assuming the cut only happens between strings. In reality, the cut may occur at any character position.
For example:
["abc", "xyz"]
The optimal answer begins in the middle of "zyx".
The implementation explicitly iterates through every index inside every candidate string, ensuring no valid rotation is missed.
Reverse Choice Changes the Global Optimum
Sometimes a string that appears smaller locally creates a larger overall result when rotated.
For example:
"abc" -> "cba"
The algorithm handles this by always trying both orientations for the string containing the cut while greedily fixing all other strings to their lexicographically maximal orientation.
This guarantees the globally optimal result is considered.