Split Concatenated Strings - Solution & Explanation
Problem Statement
You are given an array of strings strs. 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
Return the lexicographically largest string after cutting the loop, which will make the looped string into a regular one.
Specifically, to find the lexicographically largest string, you need to experience two phases:
- Concatenate all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
- 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 largest one among all the possible regular strings.
Example 1:
Input: strs = ["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".
Example 2:
Input: strs = ["abc"] Output: "cba"
Constraints:
1 <= strs.length <= 10001 <= strs[i].length <= 10001 <= sum(strs[i].length) <= 1000strs[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You receive an array of strings. Each string can either stay as is or be reversed before concatenation. After forming the final concatenated string, you can split it at any position and swap the order of the two parts. The goal is to return the lexicographically largest possible string after these operations.
Approach 1: Brute Force Enumeration (Exponential Time)
Try every possible orientation for each string: original or reversed. With n strings, that creates 2^n combinations. For each combination, concatenate the strings, then simulate every possible split point and compare the resulting rotated strings to keep the maximum lexicographic result. This approach clearly demonstrates the full search space but quickly becomes impractical. Time complexity is O(2^n * L^2) where L is the total concatenated length, and space complexity is O(L).
Approach 2: Greedy with Optimal Orientation (O(n * L^2))
The key greedy observation: for every string, keeping the lexicographically larger version between the original and its reverse will always help maximize the final result. First iterate through the array and replace each string with max(s, reverse(s)). This ensures every segment contributes the largest possible prefix when concatenated.
Next, treat each string as a potential split source. For the current index i, consider both orientations of that string (s and reverse(s)) because the split may occur inside it. Build the remaining concatenation using the already optimized orientation for other strings. Then iterate through every split position inside the chosen string and construct a candidate result: suffix + rest_of_strings + prefix. Track the maximum lexicographic string during this process.
This works because the greedy preprocessing fixes all strings except the one containing the split. Only that string might need reconsideration of orientation. If the total length of all strings is L, evaluating every split across all strings results in O(n * L^2) time in the worst case with O(L) auxiliary space.
The solution combines ideas from greedy decision making with careful iteration over string rotations and indexing within an array of words.
Recommended for interviews: The greedy approach is what interviewers expect. Mentioning the brute-force 2^n orientation search shows you understand the full problem space, but recognizing that each string should first be normalized to its lexicographically larger orientation demonstrates algorithmic insight and reduces the search dramatically.
Solution
We first traverse the string array strs. For each string s, if the reversed string t is greater than s, we replace s with t.
Then we enumerate each position i in the string array strs as a split point, dividing the string array strs into two parts: strs[i + 1:] and strs[:i]. We then concatenate these two parts to get a new string t. Next, we enumerate each position j in the current string strs[i]. The suffix part is a = strs[i][j:], and the prefix part is b = strs[i][:j]. We can concatenate a, t, and b to get a new string cur. If cur is greater than the current answer, we update the answer. This considers the case where strs[i] is reversed. We also need to consider the case where strs[i] is not reversed, i.e., concatenate a, t, and b in reverse order to get a new string cur. If cur is greater than the current answer, we update the answer.
Finally, we return the answer.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string array strs.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Orientation + All Splits | O(2^n * L^2) | O(L) | Useful for understanding the full search space or verifying correctness on small inputs |
| Greedy Orientation + Split Enumeration | O(n * L^2) | O(L) | Optimal practical solution used in interviews and competitive programming |
Video Solution
LeetCode 555 Split Concatenated Strings • chen xiang • 388 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Split Concatenated Strings easy or hard?
Split Concatenated Strings Python/Java solution
How to solve Split Concatenated Strings in O(n * L^2)?
What is the best approach for Split Concatenated Strings?
Is Split Concatenated Strings asked at Google/Amazon/Meta?
What data structure is used in Split Concatenated Strings?
What is the time complexity of Split Concatenated Strings?
Ready to solve this problem?
Practice Split Concatenated Strings with our built-in code editor and test cases.
Practice on FleetCode