555. Split Concatenated Strings


Problem Description

The problem presents a challenge where you are given an array of strings strs. The task is to concatenate these strings to form a loop, with the option of reversing any of the strings. Once the loop is created, you must cut the loop at any point and unravel it into a regular string that begins with the character at the cut point. The goal is to find the lexicographically largest string (i.e., the string that would appear last if the strings were sorted alphabetically) that can be obtained following these steps.

Intuition

The intuition behind the solution involves looking for the optimal way to arrange and possibly reverse the strings in order to maximize the lexicographical order of the final string.

Firstly, we observe that reversing a string can only be beneficial if the reversed string is lexicographically larger than the original one. With this in mind, we iterate through each string in the array and replace it with its reverse if the reversed string would come later in lexicographical order.

Next, we want to try various breakpoints to determine the largest possible string we can create. We loop through each string and consider every possible position within that string to break the loop. Once we've chosen where to break a string, there are two possible strings we can form: one that starts from the breakpoint and goes to the end of the string, then continues with the rest of the loop, followed by the start of the string to the breakpoint; and the other that is the reverse - starting from the character before the breakpoint, going backwards to the beginning, continuing with the end of the loop, and finishing with the reverse of the substring from the breakpoint to the end.

By comparing all possible breakpoints and choosing the one that yields the lexicographically largest string, we can find the solution to the problem.

The key here is to understand that the loop allows for flexible starting points and the option to include reversed versions of strings, which can affect the final result.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The implementation of the solution uses a step-by-step strategy to ensure that we analyze all possible strings that can be created through reversing and concatenation.

Step 1: Optimize the Individual Strings

As the first step, we iterate through the given array strs and decide for each individual string if it should be reversed. This decision is based on a simple comparison: if the reversed string is lexicographically larger than the original string, then we replace the original with its reversed version. The comparison s[::-1] > s is used for this, and list comprehension in Python makes this step concise and efficient.

1strs = [s[::-1] if s[::-1] > s else s for s in strs]

Step 2: Find the Lexicographically Largest String

Now that we have an optimized version of the array strs, we want to concatenate the strings to form loops and check every possible breakpoint to find the largest string. The loop has two parts:

  • A part before the breakpoint (a)
  • A part after the breakpoint (b)

To explore all options, we iterate over the array and for each string, we again iterate over each character to consider all possible breakpoints within that string.

For each breakpoint, we create two potential strings:

  1. One that starts from the breakpoint to the end of the string and continues with the rest of the strings in the array (a + t + b)
  2. The reverse scenario, which starts with the reverse of the string from the beginning to the breakpoint, then continues with the rest, and finishes with the reverse of the substring from the breakpoint to the end (b[::-1] + t + a[::-1]).

In the code, t represents the concatenation of the strings in the array except for the current string being processed. It is obtained by concatenating the strings following the current string and those before it.

1for i, s in enumerate(strs):
2    t = ''.join(strs[i + 1 :]) + ''.join(strs[:i])
3    for j in range(len(s)):
4        a = s[j:]    # Part after the breakpoint
5        b = s[:j]    # Part before the breakpoint
6        ans = max(ans, a + t + b)
7        ans = max(ans, b[::-1] + t + a[::-1])

We use the max() function to keep track of the lexicographically largest string encountered so far. By the end of these nested loops, ans will hold the lexicographically largest string that can be formed based on the given rules.

Data Structures and Patterns

  • String and List manipulations are heavily used in this problem.
  • The inherent ordered nature of strings in Python is leveraged to make lexicographical comparisons.
  • List comprehension is used for its readability and efficiency in replacing elements based on a condition.
  • Nested loops are utilized to consider all possible strings resulting from different breakpoints.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Consider the following example with an array of strings strs = ["bca", "ada", "acb"]. The task is to find the lexicographically largest string that can be obtained by reversing any of the strings, forming a loop, cutting the loop at any point, and unraveling it into a string.

Optimizing Individual Strings

Firstly, we determine if reversing any of the strings would produce a larger lexicographical string:

  • Original: "bca", Reversed: "acb" -> Reversed is larger, so we use "acb".
  • Original: "ada", Reversed: "ada" -> Both are the same, so no change is made.
  • Original: "acb", Reversed: "bca" -> Original is larger, so no change is made.

Now, our optimized array strs looks like this: ["acb", "ada", "acb"].

Finding the Lexicographically Largest String

We now construct loops and check every possible breakpoint:

Starting with the first string "acb" and breaking at each point, we get:

  1. Breakpoint after "a": String = "cb" + "adaacb" + "a" = "cbadaacba" (Reverse = "abcaadabc")
  2. Breakpoint after "c": String = "b" + "adaacb" + "ac" = "badaacb" (Reverse = "caadaacdab")
  3. Breakpoint after "b": String = "" + "adaacb" + "acb" = "adaacbacb"

We do this for each string in our optimized array. Then, we compare all these strings along with their reverse versions to find the maximum:

First String ("acb"):

  • "cbadaacba" and "abcaadabc" -> Maximum is "cbadaacba"
  • "badaacb" and "caadaacdab" -> Maximum is "caadaacdab"
  • "adaacbacb" -> Already the entire string, no reverse needed.

Second String ("ada"): Similar tests are conducted with "ada" as the breaking point, but none will be larger than "caadaacdab", so for brevity's sake, we will not list them.

Third String ("acb"): Similar tests are conducted with "acb" as the breaking point, but again, none will be larger than "caadaacdab".

After comparing all possible breakpoints and their reversed counterparts from each string, we find that "caadaacdab" is the lexicographically largest string. This string will be kept as the value of ans.

Result

The solution returns that the lexicographically largest string possible by following the given method on the array ["bca", "ada", "acb"] is "caadaacdab".

Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the maximum element can be found in:

Python Solution

1class Solution:
2    def splitLoopedString(self, strings):
3        # Ensure each string in the list is the lexicographically larger between
4        # its original and reversed version
5        strings = [string[::-1] if string[::-1] > string else string for string in strings]
6      
7        # Store the current best result by joining all the strings
8        best_result = ''.join(strings)
9      
10        # Iterate through each string in the list
11        for index, string in enumerate(strings):
12            # Concatenate the parts of the list that come after and before the current string
13            tail = ''.join(strings[index + 1 :]) + ''.join(strings[:index])
14          
15            # Iterate through each character in the current string
16            for j in range(len(string)):
17                # Divide the current string into two parts by the current character
18                part1 = string[j:]  # Part after the current character
19                part2 = string[:j]  # Part before the current character
20              
21                # Create new strings for comparison and update best_result if needed
22                # by combining the current split and the tail parts
23                # Original order of the current string
24                best_result = max(best_result, part1 + tail + part2)
25                # Reverse the order of the current string
26                best_result = max(best_result, part2[::-1] + tail + part1[::-1])
27      
28        # Return the lexicographically largest string
29        return best_result
30

Java Solution

1class Solution {
2    public String splitLoopedString(String[] strs) {
3        // Length of the strs array.
4        int n = strs.length;
5      
6        // Loop through each string in strs.
7        for (int i = 0; i < n; ++i) {
8            String str = strs[i]; // Current string.
9            String reversedStr = new StringBuilder(str).reverse().toString(); // Reversed string.
10          
11            // Replace the string with its reversed counterpart if the reversed is lexicographically greater.
12            if (str.compareTo(reversedStr) < 0) {
13                strs[i] = reversedStr;
14            }
15        }
16      
17        // This will hold the answer, starting as an empty string.
18        String result = "";
19      
20        // This loop constructs strings by splitting the loop at each possible string,
21        // and at each possible split position within a string.
22        for (int i = 0; i < n; ++i) {
23            String originalStr = strs[i]; // Get the current string to split on.
24            StringBuilder remainingStrBuilder = new StringBuilder();
25          
26            // Append all strings in the array after the current string to the remaining string builder.
27            for (int j = i + 1; j < n; ++j) {
28                remainingStrBuilder.append(strs[j]);
29            }
30          
31            // Append all strings in the array before the current string to the remaining string builder.
32            for (int j = 0; j < i; ++j) {
33                remainingStrBuilder.append(strs[j]);
34            }
35          
36            // Convert the StringBuilder to a String as it will be appended to both possibilities.
37            String remainingStr = remainingStrBuilder.toString();
38          
39            // Try all possible splits within the current string.
40            for (int j = 0; j < originalStr.length(); ++j) {
41                String start = originalStr.substring(j);
42                String end = originalStr.substring(0, j);
43              
44                // Combine the start of the split, the remaining strings, and the end of the split.
45                String combination = start + remainingStr + end;
46                // If the combination is lexicographically larger than the result, update the result.
47                if (result.compareTo(combination) < 0) {
48                    result = combination;
49                }
50              
51                // Reverse the start and end chunks before combining.
52                String reverseCombination = new StringBuilder(end).reverse().toString()
53                                        + remainingStr
54                                        + new StringBuilder(start).reverse().toString();
55                                      
56                // If the reverse combination is lexicographically larger than the result, update the result.
57                if (result.compareTo(reverseCombination) < 0) {
58                    result = reverseCombination;
59                }
60            }
61        }
62      
63        // Return the lexicographically largest combination found.
64        return result;
65    }
66}
67

C++ Solution

1#include <string>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7    string splitLoopedString(vector<string>& strs) {
8        // First, ensure every string in strs is in its lexicographically maximum form,
9        // whether its original form or its reverse.
10        for (string &str : strs) {
11            string reversedStr{str.rbegin(), str.rend()};
12            str = max(str, reversedStr);
13        }
14
15        const int n = strs.size(); // Store the size of strs
16        string result = ""; // Initialize the result string which will hold the max lexicographical string
17
18        // Iterate over each string in strs
19        for (int i = 0; i < n; ++i) {
20            const string &currentStr = strs[i]; // Reference to current string
21
22            // Construct the rest of the string except for the current string
23            string rest = "";
24            for (int j = i + 1; j < n; ++j) {
25                rest += strs[j];
26            }
27            for (int j = 0; j < i; ++j) {
28                rest += strs[j];
29            }
30
31            // Iterate over each character in the current string to try all splits
32            for (int j = 0; j < currentStr.size(); ++j) {
33                string leftPart = currentStr.substr(j); // Left part of the split current string
34                string rightPart = currentStr.substr(0, j); // Right part of the split current string
35
36                // Form a new string by choosing the left part first, then rest, and then right part
37                string candidate1 = leftPart + rest + rightPart;
38                // Check if it's larger lexicographically than result
39                if (result < candidate1) {
40                    result = candidate1;
41                }
42
43                // We then try another combination by reversing the left and right parts
44                reverse(leftPart.begin(), leftPart.end());
45                reverse(rightPart.begin(), rightPart.end());
46                // Form a new string by choosing the right part first, then rest, and then left part
47                string candidate2 = rightPart + rest + leftPart;
48                // Check if it's larger lexicographically than result
49                if (result < candidate2) {
50                    result = candidate2;
51                }
52            }
53        }
54
55        // At the end of the loop, result will contain the maximum lexicographical string possible
56        return result;
57    }
58};
59

Typescript Solution

1// You should include relevant TypeScript type definitions for the string arrays
2
3// Ensure every string in the array is in its lexicographically maximum form,
4// either its original form or its reverse.
5function makeStringsLexicographicallyMaximum(strs: string[]): void {
6    strs.forEach((str, index, array) => {
7        const reversedStr = str.split('').reverse().join('');
8        array[index] = reversedStr > str ? reversedStr : str;
9    });
10}
11
12// Finds the lexicographically maximum string by splitting and reordering
13function splitLoopedString(strs: string[]): string {
14    makeStringsLexicographicallyMaximum(strs); // Preprocess the strings
15
16    const n: number = strs.length; // Store the size of the strs array
17    let result: string = ""; // Initialize the result string to hold the maximum lexicographical string
18
19    // Iterate over each string in the strs array
20    for (let i = 0; i < n; ++i) {
21        const currentStr: string = strs[i]; // Current string in the iteration
22
23        // Construct the rest of the string excluding the current string
24        let rest: string = "";
25        for (let j = i + 1; j < n; ++j) {
26            rest += strs[j];
27        }
28        for (let j = 0; j < i; ++j) {
29            rest += strs[j];
30        }
31
32        // Iterate over each character in the current string to test all possible splits
33        for (let j = 0; j < currentStr.length; ++j) {
34            let leftPart = currentStr.substring(j); // Left part of the current string after split
35            let rightPart = currentStr.substring(0, j); // Right part of the current string after split
36
37            // Form a new string by choosing the left part, then the rest, and then the right part
38            let candidate1 = leftPart + rest + rightPart;
39            // Update the result if the new string is greater lexicographically
40            if (result < candidate1) {
41                result = candidate1;
42            }
43
44            // Try another combination by reversing the order of left and right parts
45            let leftPartReversed = leftPart.split('').reverse().join('');
46            let rightPartReversed = rightPart.split('').reverse().join('');
47
48            // Form a new string by choosing the reversed right part, the rest, and then the reversed left part
49            let candidate2 = rightPartReversed + rest + leftPartReversed;
50            // Update result if the new combination is larger lexicographically
51            if (result < candidate2) {
52                result = candidate2;
53            }
54        }
55    }
56
57    // Return the maximum lexicographical string possible
58    return result;
59}
60
Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Time and Space Complexity

Time Complexity

The time complexity of the initial string reversal in the list comprehension is O(n * m), where n is the number of strings in the list and m is the average length of the strings, as reversal takes O(m) and it is done for each of the n strings.

Then, we iterate over each of the n strings, and for each string, we perform a series of string concatenations. The concatenation t = ''.join(strs[i + 1 :]) + ''.join(strs[:i]) occurs n times and each time it has a cost of O(k), where k is the total length of the strings in the array strs. This step contributes O(n * k) to the time complexity.

Inside the outer loop, we further loop within each string having an average length m, performing multiple operations. The generation of substrings a = s[j:] and b = s[:j] is done mn times and each takes O(m). This contributes another O(m^2 * n).

Finally, max operations and reversals are done within this inner loop, which again contributes a factor of m for each string operation.

Adding all up, we have: Total Time Complexity = O(n * m) + O(n * k) + O(m^2 * n) In the worst case, where k is large, the term O(n * k) will dominate, so the final time complexity can be approximated as O(n * k).

Space Complexity

The space complexity of the solution is determined by the storage needed for the modified strings list and the temporary variables used for concatenation and comparison. String reversal and list comprehension create a new list of the same size, O(n). The temporary variables t, a, and b can together hold up to O(k) space, where k is the total length of all strings. The max function does not use additional space proportional to the input size.

Thus, the space complexity is O(n + k).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫