Problem

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:

  1. Concatenate all the strings into a loop, where you can reverse some strings or not and connect them in the same order as given.
  2. 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.

Examples

Example 1:

1
2
3
4

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:

1
2

Input: strs = ["abc"]
Output: "cba"

Constraints:

  • 1 <= strs.length <= 1000
  • 1 <= strs[i].length <= 1000
  • 1 <= sum(strs[i].length) <= 1000
  • strs[i] consists of lowercase English letters.

Solution

Method 1 – Greedy Cut and Reverse

Intuition

To get the lexicographically largest string, we need to consider every possible way to reverse each string and every possible cut point in the loop. For each string, try both its original and reversed form, and for each character in that string, treat it as the cut point. By greedily choosing the best configuration for each string and cut, we can efficiently find the answer.

Approach

  1. For each string in the array, consider both its original and reversed form.
  2. For each character position in the current string, treat it as the cut point.
  3. Build the looped string by concatenating the chosen forms of all strings, starting from the cut point and wrapping around.
  4. For each configuration, compare with the current best answer and update if it is lexicographically larger.
  5. Return the largest string found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    string splitLoopedString(vector<string>& strs) {
        int n = strs.size();
        for (auto& s : strs) {
            string rev = s;
            reverse(rev.begin(), rev.end());
            if (rev > s) s = rev;
        }
        string ans;
        for (int i = 0; i < n; ++i) {
            string orig = strs[i], rev = orig;
            reverse(rev.begin(), rev.end());
            for (auto& cur : {orig, rev}) {
                for (int k = 0; k < cur.size(); ++k) {
                    string t = cur.substr(k);
                    for (int j = 1; j < n; ++j) {
                        t += strs[(i + j) % n];
                    }
                    t += cur.substr(0, k);
                    if (t > ans) ans = t;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

func splitLoopedString(strs []string) string {
    n := len(strs)
    for i := range strs {
        rev := reverse(strs[i])
        if rev > strs[i] {
            strs[i] = rev
        }
    }
    ans := ""
    for i := 0; i < n; i++ {
        orig := strs[i]
        rev := reverse(orig)
        for _, cur := range []string{orig, rev} {
            for k := 0; k < len(cur); k++ {
                t := cur[k:]
                for j := 1; j < n; j++ {
                    t += strs[(i+j)%n]
                }
                t += cur[:k]
                if t > ans {
                    ans = t
                }
            }
        }
    }
    return ans
}
func reverse(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;
class Solution {
    public String splitLoopedString(String[] strs) {
        int n = strs.length;
        for (int i = 0; i < n; ++i) {
            String rev = new StringBuilder(strs[i]).reverse().toString();
            if (rev.compareTo(strs[i]) > 0) strs[i] = rev;
        }
        String ans = "";
        for (int i = 0; i < n; ++i) {
            String orig = strs[i], rev = new StringBuilder(orig).reverse().toString();
            for (String cur : new String[]{orig, rev}) {
                for (int k = 0; k < cur.length(); ++k) {
                    StringBuilder sb = new StringBuilder(cur.substring(k));
                    for (int j = 1; j < n; ++j) {
                        sb.append(strs[(i + j) % n]);
                    }
                    sb.append(cur.substring(0, k));
                    String t = sb.toString();
                    if (t.compareTo(ans) > 0) ans = t;
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun splitLoopedString(strs: Array<String>): String {
        val n = strs.size
        for (i in strs.indices) {
            val rev = strs[i].reversed()
            if (rev > strs[i]) strs[i] = rev
        }
        var ans = ""
        for (i in 0 until n) {
            val orig = strs[i]
            val rev = orig.reversed()
            for (cur in listOf(orig, rev)) {
                for (k in cur.indices) {
                    var t = cur.substring(k)
                    for (j in 1 until n) {
                        t += strs[(i + j) % n]
                    }
                    t += cur.substring(0, k)
                    if (t > ans) ans = t
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def splitLoopedString(self, strs: list[str]) -> str:
        n = len(strs)
        for i in range(n):
            rev = strs[i][::-1]
            if rev > strs[i]:
                strs[i] = rev
        ans = ''
        for i in range(n):
            orig = strs[i]
            rev = orig[::-1]
            for cur in [orig, rev]:
                for k in range(len(cur)):
                    t = cur[k:]
                    for j in range(1, n):
                        t += strs[(i + j) % n]
                    t += cur[:k]
                    if t > ans:
                        ans = t
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn split_looped_string(strs: Vec<String>) -> String {
        let n = strs.len();
        let mut strs = strs;
        for i in 0..n {
            let rev: String = strs[i].chars().rev().collect();
            if rev > strs[i] {
                strs[i] = rev;
            }
        }
        let mut ans = String::new();
        for i in 0..n {
            let orig = &strs[i];
            let rev: String = orig.chars().rev().collect();
            for cur in [orig, &rev] {
                for k in 0..cur.len() {
                    let mut t = String::from(&cur[k..]);
                    for j in 1..n {
                        t.push_str(&strs[(i + j) % n]);
                    }
                    t.push_str(&cur[..k]);
                    if t > ans {
                        ans = t;
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    splitLoopedString(strs: string[]): string {
        const n = strs.length;
        for (let i = 0; i < n; ++i) {
            const rev = strs[i].split('').reverse().join('');
            if (rev > strs[i]) strs[i] = rev;
        }
        let ans = '';
        for (let i = 0; i < n; ++i) {
            const orig = strs[i];
            const rev = orig.split('').reverse().join('');
            for (const cur of [orig, rev]) {
                for (let k = 0; k < cur.length; ++k) {
                    let t = cur.slice(k);
                    for (let j = 1; j < n; ++j) {
                        t += strs[(i + j) % n];
                    }
                    t += cur.slice(0, k);
                    if (t > ans) ans = t;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N * L^2) – N is the number of strings, L is the average length. For each string and each character, we build a candidate string.
  • 🧺 Space complexity: O(L * N) – For storing the candidate and reversed strings.