Split Concatenated Strings

#3 Most AskedMedium

Split Concatenated Strings #3 Most Asked

Medium

3 views

Topics:

StringsGreedy AlgorithmsArrays

Given an array of strings strs, you could concatenate these strings together in any order to form a loop. Among all the possible loops, you need to find the lexicographically largest string after cutting the loop, which will make the looped string into a regular one.

Specifically, to form a loop, you can concatenate strs[0], strs[1], ..., strs[n-1] in any order, where n is the length of strs. Also, for each string strs[i], you can choose to reverse it or not.

After forming a loop, you can cut it at any point. The cutting point will be the starting point of the looped string.

Your job is to find the lexicographically largest one among all the possible choices.

Example 1:

Input: strs = ["abc", "xyz"]
Output: "zyxcba"
Explanation: You can get the looped string "-abc-xyz-" by concatenating "abc" and "xyz" in order. 
After choosing the best split point, we can get "zyxcba", which is from "xyz" + "abc".
- For each string, we can choose "abc" or "cba", "xyz" or "zyx".
- If we concatenate "abc" and "xyz", we get "abcxyz". Cut it at 'x' to get "xyzabc".
- If we concatenate "cba" and "xyz", we get "cbaxyz". Cut it at 'x' to get "xyzcba".
- If we concatenate "abc" and "zyx", we get "abczyx". Cut it at 'z' to get "zyxabc".
- If we concatenate "cba" and "zyx", we get "cbazyx". Cut it at 'z' to get "zyxcba".

Constraints:

1 <= strs.length <= 1000
1 <= strs[i].length <= 1000
strs[i] consists of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

May each word be replaced by its reverse when that reverse is lexicographically larger?
Is the relative order of the words kept, aside from which word is cut and whether that word is flipped?
Does the largest result mean ordinary dictionary order, compared from the first character onward?
Can the cut begin at any character of the chosen word, including the first character?
Should a single-word list still compare that word with its reverse?

Brute Force Solution

Approach

Each word is first replaced by the larger of itself and its reverse. The search then rotates which word is the one being cut, while the other words stay in their circular order after that word. For both orientations of the cut word, every cut position is joined back together and the largest string is kept.

Here's how the algorithm would work step-by-step:

Replace every word by the larger of the word and its reverse.
Start the winner as an empty string.
For each word in order, take the words after it and then the words before it as the uncut remainder.
Consider both the oriented word and its reverse as the word that will be cut.
For every character position in that form, split it into a suffix and a prefix.
Build the candidate as the suffix, then a fresh join of the remainder, then the prefix.
Replace the winner when the candidate is strictly larger.

Code Implementation

class Solution:
    def splitLoopedString(self, string_list: list[str]) -> str:
        # Step 1: For each word, choose the lexicographically larger of the word and its reverse.
        # This ensures each individual component word is maximized before concatenation.
        best_orientation_words = [max(word, word[::-1]) for word in string_list]

        largest_word_so_far = ""

        # Step 2 & 3: Try every word as the starting point of the circular arrangement.
        for start_index in range(len(best_orientation_words)):
            current_start_word = best_orientation_words[start_index]
            rest_of_words = best_orientation_words[start_index + 1:] + best_orientation_words[:start_index]
            
            # Step 4: For each potential starting word, check both its original and reversed forms.
            # The optimal cut might be within a word that was reversed in step 1.
            for potential_word_form in [current_start_word, current_start_word[::-1]]:
                for cut_point in range(len(potential_word_form)):
                    first_part = potential_word_form[cut_point:]
                    second_part = "".join(rest_of_words)
                    third_part = potential_word_form[:cut_point]
                    
                    # Step 5: Construct the full candidate string from the cut parts and compare.
                    # This systematically generates every possible string from the circular arrangement.
                    candidate_string = first_part + second_part + third_part
                    if candidate_string > largest_word_so_far:
                        largest_word_so_far = candidate_string
        
        # Step 6: After checking all possibilities, we have found the lexicographically largest string.
        return largest_word_so_far

Big(O) Analysis

Time Complexity

O(L^2) – Orienting every word reverses each of them once, which is linear in the total number of characters L. Each word is chosen as the cut word once, and both orientations are cut at every character, so the number of cuts is proportional to L. At every cut the other words are joined again and the full candidate is built, each of which copies on the order of L characters. A linear number of cuts times a linear copy is O(L^2). The initial orientation work is absorbed by that bound.

Space Complexity

O(L) – The oriented words store one copy of the input characters. The remainder list holds references to those words rather than a new copy of every rotation at the same time. Each candidate is a single string of length L and can be discarded after it is compared, aside from the winner. The winner itself is at most L characters. Extra space is O(L).

Optimal Solution

Approach

Each word is oriented to the larger of the word and its reverse, with a tie keeping the reverse, which is the same text. For each chosen word the other words are concatenated once in their original relative order. Both orientations of the chosen word are then split at every character, and the best suffix-plus-remainder-plus-prefix string is kept.

Here's how the algorithm would work step-by-step:

Orient each word to whichever of the word and its reverse compares larger.
Start the best string empty.
For each word, concatenate the words before it and the words after it a single time.
Try the oriented word and also the reverse of that oriented word.
At each character, take the suffix as the new beginning and the prefix as the new ending.
Form the candidate from that suffix, the prejoined remainder, and the prefix.
Keep the candidate when it is strictly greater than the best string.

Code Implementation

def split_concatenated_strings(list_of_strings):
    # First, optimize each individual string by choosing its lexicographically larger orientation.
    optimized_words = [word if word > word[::-1] else word[::-1] for word in list_of_strings]

    largest_string_found = ""

    for word_index, current_word in enumerate(optimized_words):
        remaining_words = optimized_words[:word_index] + optimized_words[word_index+1:]
        concatenated_remainder = "".join(remaining_words)

        # Test both the original and reversed forms of the current word as the split point.
        for variant_to_test in [current_word, current_word[::-1]]:
            for split_position in range(len(variant_to_test)):
                # This rotation simulates starting the final string at the current character.
                suffix_part = variant_to_test[split_position:]
                prefix_part = variant_to_test[:split_position]

                # A candidate string is formed by placing the suffix first, then the other words, then the prefix.
                candidate_string = suffix_part + concatenated_remainder + prefix_part
                
                if candidate_string > largest_string_found:
                    largest_string_found = candidate_string

    return largest_string_found

Big(O) Analysis

Time Complexity

O(L^2) – Orientation is linear in the total character count L. Joining the other words once per chosen word costs linear work per word, and a word has at least one character in the usual case, so that part is at most quadratic. Every character of every word is still used as a cut in two orientations, which is a linear number of cuts. Each cut allocates a new string of length L. The cuts dominate and the bound is O(L^2).

Space Complexity

O(L) – The oriented list is another copy of the characters. One remainder string of length about L is live for the cuts of a single word and is replaced for the next word. The candidate and the retained winner are also length L. No matrix of all rotations is stored. Extra space is O(L).

Edge Cases

Case	How to Handle
The list contains one word	Compare that word with its reverse at every cut and return the larger text.
A word equals its reverse	Keep that single orientation, because flipping it does not change the characters.
The cut is on the first character of the chosen word	Start the candidate with the entire chosen word, followed by the other words and an empty tail.
A new candidate ties the current winner	Keep the existing winner, because only a strictly larger string replaces it.
The best cut sits inside the flipped form of a word	Test both orientations of the chosen word at every character before deciding.
Every word is one character	Each cut is just that character followed by the other characters in their kept order.

The list contains one word

How to Handle:

Compare that word with its reverse at every cut and return the larger text.

A word equals its reverse

How to Handle:

Keep that single orientation, because flipping it does not change the characters.

The cut is on the first character of the chosen word

How to Handle:

Start the candidate with the entire chosen word, followed by the other words and an empty tail.

A new candidate ties the current winner

How to Handle:

Keep the existing winner, because only a strictly larger string replaces it.

The best cut sits inside the flipped form of a word

How to Handle:

Test both orientations of the chosen word at every character before deciding.

Every word is one character

How to Handle:

Each cut is just that character followed by the other characters in their kept order.