Split Concatenated Strings

medium array string greedy

Problem

Pick one rotation/direction per string and concatenate; cut at any position. Return the lexicographically largest cyclic cut.

Inputstrs = ["abc","xyz"]

Output"zyxcba"

Two-pass: form each piece's best orientation, then for every (i, cut) inside that piece compose suffix(i, cut) + rest + prefix(i, cut).

strings (comma-separated)

def split_loopy_string(strs):
    bigger = [max(s, s[::-1]) for s in strs]
    best = ""
    for i in range(len(strs)):
        rest = "".join(bigger[i+1:] + bigger[:i])
        for s in (strs[i], strs[i][::-1]):
            for k in range(len(s) + 1):
                cand = s[k:] + rest + s[:k]
                if cand > best: best = cand
    return best

function splitLoopedString(strs) {
  const bigger = strs.map(s => {
    const r = s.split("").reverse().join("");
    return s > r ? s : r;
  });
  let best = "";
  for (let i = 0; i < strs.length; i++) {
    const rest = bigger.slice(i + 1).concat(bigger.slice(0, i)).join("");
    for (const orient of [strs[i], strs[i].split("").reverse().join("")]) {
      for (let k = 0; k <= orient.length; k++) {
        const cand = orient.slice(k) + rest + orient.slice(0, k);
        if (cand > best) best = cand;
      }
    }
  }
  return best;
}

class Solution {
    public String splitLoopedString(String[] strs) {
        String[] bigger = new String[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String r = new StringBuilder(strs[i]).reverse().toString();
            bigger[i] = strs[i].compareTo(r) >= 0 ? strs[i] : r;
        }
        String best = "";
        for (int i = 0; i < strs.length; i++) {
            StringBuilder rest = new StringBuilder();
            for (int j = i + 1; j < strs.length; j++) rest.append(bigger[j]);
            for (int j = 0; j < i; j++) rest.append(bigger[j]);
            String r = new StringBuilder(strs[i]).reverse().toString();
            for (String orient : new String[]{strs[i], r}) {
                for (int k = 0; k <= orient.length(); k++) {
                    String cand = orient.substring(k) + rest + orient.substring(0, k);
                    if (cand.compareTo(best) > 0) best = cand;
                }
            }
        }
        return best;
    }
}

string splitLoopedString(vector& strs) {
    int n = strs.size();
    vector bigger(n);
    for (int i = 0; i < n; i++) { string r = string(strs[i].rbegin(), strs[i].rend()); bigger[i] = max(strs[i], r); }
    string best;
    for (int i = 0; i < n; i++) {
        string rest;
        for (int j = i + 1; j < n; j++) rest += bigger[j];
        for (int j = 0; j < i; j++) rest += bigger[j];
        string r = string(strs[i].rbegin(), strs[i].rend());
        for (auto& orient : vector{strs[i], r}) {
            for (int k = 0; k <= (int)orient.size(); k++) {
                string cand = orient.substr(k) + rest + orient.substr(0, k);
                if (cand > best) best = cand;
            }
        }
    }
    return best;
}

Explanation

We loop all the strings into a cycle, choose each one's orientation (forward or reversed), then make a single cut somewhere and read the loop starting from that cut. We want the lexicographically largest result.

The key shortcut: for every string except the one we cut inside, orientation is independent and we should just take its bigger version, bigger[i] = max(s, reverse(s)). Only the string where the cut lands needs both orientations tried, because the cut interacts with its direction.

So we fix each string i as the "cut piece". The other strings, in cyclic order after i, are pre-maximized and joined into rest. Then for both orientations of string i and every cut position k, we build candidate = s[k:] + rest + s[:k] and keep the largest seen.

Example: strs = ["abc","xyz"]. Each piece maximized is "cba" and "zyx". Cutting inside the xyz piece reversed to zyx at the front, with cba as the rest, yields "zyxcba", the biggest cut.

Trying every piece, both orientations, and every cut covers all distinct results, so the maximum we record is the true answer.

Time: O(N·L) Space: O(N·L)