35岁被公司裁了，但拿到了40万赔偿金，失业在家4个月，突然看到丈母娘给媳妇儿的信息，人要崩溃了。网友：丈母娘太坏了！

面试题：分割连接字符串

有个题看着像字符串拼接，真写起来最容易漏一刀：分割连接字符串。

给你一组字符串，每个字符串可以选择正着放，也可以反着放。全部连起来之后，再从任意位置切一刀，把后半段挪到前面，问能得到的字典序最大的字符串是什么。

这题我第一眼不太信贪心只扫一遍就能完事。因为“反转”和“切分”两个动作叠在一起，切的位置不同，前缀字符就变了，字典序也跟着变。

比如：

["abc", "xyz"]

abc 可以变成 cba，xyz 也可以变成 zyx。

你最后不是简单拼一个最大串，而是要考虑从哪一个字符开始。

这类题我一般先拆成两层。

第一层，除了当前准备切开的字符串，其他字符串都应该选自己和反转里字典序更大的那个。这个没什么好犹豫的，它们在候选串中是一整段出现，当然越大越好。

第二层，当前字符串要特殊处理。因为切口可能落在它里面，所以它不能只取最大方向，正着和反着都要试。

代码可以这么写：

publicclassSplitJoinString{

public String largestLoop(String[] parts){
int n = parts.length;
        String[] best = new String[n];

for (int i = 0; i < n; i++) {
            String rev = reverse(parts[i]);
            best[i] = parts[i].compareTo(rev) >= 0 ? parts[i] : rev;
        }

        String ans = "";

for (int i = 0; i < n; i++) {
            String leftBlock = join(best, i + 1, n) + join(best, 0, i);

            String raw = parts[i];
            String rev = reverse(raw);

            ans = scanCut(raw, leftBlock, ans);
            ans = scanCut(rev, leftBlock, ans);
        }

return ans;
    }

private String scanCut(String cur, String middle, String ans){
for (int cut = 0; cut < cur.length(); cut++) {
            String candidate = cur.substring(cut) + middle + cur.substring(0, cut);
if (candidate.compareTo(ans) > 0) {
                ans = candidate;
            }
        }
return ans;
    }

private String join(String[] arr, int l, int r){
        StringBuilder sb = new StringBuilder();
for (int i = l; i < r; i++) {
            sb.append(arr[i]);
        }
return sb.toString();
    }

private String reverse(String s){
returnnew StringBuilder(s).reverse().toString();
    }
}

这里最容易写错的是这一句：

ans = scanCut(raw, leftBlock, ans);
ans = scanCut(rev, leftBlock, ans);

当前字符串一定要两个方向都试。有人会先把每个字符串都换成 max(s, reverse(s))，然后只在这个结果上切。这样会漏答案。

原因很简单，字符串整体更大，不代表它从某个位置切开后仍然更大。

比如某个串正着开头小，但中间藏了一个更大的字符；反过来整体看着大，切出来的开头反而不行。这种题，字典序看的就是切完之后第一个不同字符，不能提前替当前串做决定。

整个流程其实就一句话：枚举哪一段被切开，其他段取最优；被切开的这一段，正反两种方向逐字符试。

时间复杂度不算吓人。设总字符数是 L，外层枚举字符串，内层枚举切点，候选串长度也是 L，直接写大概是 O(L^2)。面试题一般够用。