⚡Flashcard Drill➔
NeetCode #165LC-555MediumArrays & Hashing
← Back to All Problems

#165 · #555 · Split Concatenated Strings(分割连接字符串)

📌 Problem Statement & Constraints

Given a list of strings strs, concatenate them in order and then cut the result at some position to form a single loop, which can be read starting anywhere. Each individual string may be reversed before concatenation. Return the lexicographically largest string obtainable. Constraints: 1 <= strs.length <= 1000, 1 <= strs[i].length <= 1000, total length at most 1000.

💡 Core Algorithmic Approaches

  1. Only the string that is split can benefit from a rotation; all other strings are best used in their lexicographically larger orientation.
  2. So precompute best[i] = max(strs[i], reversed(strs[i])) for each string.
  3. For each candidate split string i, and for both orientations of it, try every split point k: the result is s[k:] + middle + s[:k], where middle is the concatenation of the other strings' best orientations in their original order.
  4. Take the maximum over all choices. The total work is O(total_length^2) in the worst case, which the small constraints allow.

💻 Benchmark Python3 Implementation

class Solution:
    def splitLoopedString(self, strs: List[str]) -> str:
        best = [max(s, s[::-1]) for s in strs]
        n = len(strs)
        res = ""
        for i in range(n):
            middle = "".join(best[i + 1:]) + "".join(best[:i])
            for cand in (strs[i], strs[i][::-1]):   # both orientations
                for k in range(len(cand)):
                    cur = cand[k:] + middle + cand[:k]
                    if cur > res:
                        res = cur
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(L^2) where L is the total length: for each of the n strings we try every rotation, and each candidate costs O(L) to build. With L <= 1000 this is at most about 10^6 character operations.
💾 Space Complexity
O(L) for the candidate strings.

⚠️ Interview Pitfalls & Follow-ups

  • Reversing every string: only the split string may be reversed in a way that matters, but the others should use their better orientation, not necessarily the reversed one.
  • Trying every rotation of every string: only the split string needs rotation; rotating the others is redundant because they are not at the boundary.
  • Forgetting the middle strings' best orientation: using the original orientation would miss better results.
  • Assuming the split string must be reversed: both orientations must be tried, since sometimes the original is better.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems