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
- Only the string that is split can benefit from a rotation; all other strings are best used in their lexicographically larger orientation.
- So precompute
best[i] = max(strs[i], reversed(strs[i]))for each string. - For each candidate split string
i, and for both orientations of it, try every split pointk: the result iss[k:] + middle + s[:k], wheremiddleis the concatenation of the other strings' best orientations in their original order. - 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.