Problem Description
Explanation
To solve this problem, we need to consider each string in the given array and examine all possible rotations. For each string, we have two choices: either keep the original string as is or reverse it. We iterate through all possibilities and choose the one that gives us the maximum lexicographical order when combined.
The key idea is to consider all possible rotations for each string and compare the result with the concatenation of other strings. We can achieve this by looping through the strings, generating all possible combinations, and keeping track of the maximum result.
Algorithm:
- Initialize an empty string
resultto store the final concatenated string. - Iterate through each string in the given array:
- For each string, generate all possible rotations by considering the string as is and its reverse.
- For each rotation, concatenate it with all subsequent strings in all possible orders.
- Compare the current result with the maximum lexicographical order and update if necessary.
- Return the final result string.
Time Complexity: O(n^2 * m), where n is the number of strings in the array and m is the average length of a string.
Space Complexity: O(n * m), where n is the number of strings in the array and m is the average length of a string.
Solutions
class Solution {
public String splitLoopedString(String[] strs) {
int n = strs.length;
StringBuilder result = new StringBuilder();
for (int i = 0; i < n; i++) {
String reverse = new StringBuilder(strs[i]).reverse().toString();
for (String s : new String[] {strs[i], reverse}) {
StringBuilder temp = new StringBuilder();
for (int j = i + 1; j < n; j++) {
temp.append(strs[j]);
}
for (int j = 0; j < i; j++) {
temp.append(strs[j]);
}
for (int k = 0; k < s.length(); k++) {
StringBuilder cur = new StringBuilder();
cur.append(s.substring(k));
for (int j = i + 1; j < n; j++) {
cur.append(strs[j]);
}
for (int j = 0; j < i; j++) {
cur.append(strs[j]);
}
cur.append(s.substring(0, k));
if (cur.toString().compareTo(temp.toString()) > 0) {
temp = cur;
}
}
if (temp.toString().compareTo(result.toString()) > 0) {
result = temp;
}
}
}
return result.toString();
}
}Related LeetCode Problems
Loading editor...