二进制串重排：追加再反转

题目

给一个只由字符 '0' 和 '1' 组成的字符串 S（题面里也叫 shipmentData）。用它按下面的规则构造另一个字符串 finalS：从空串开始，从左到右依次取 S 的每个字符 c，先把 c 接到 finalS 的末尾，再把整个 finalS 反转。

S 里的字符可以任意重新排列。题目要求找一种排法，使最后得到的 finalS（题面里也叫 finalSequence）字典序（lexicographical order）最大。按字典序比较两个串，就是像查字典那样从第一个字符开始逐位比较，比到第一个不同的位置时，这一位字符较大的串更大。这里所有候选的 finalS 长度都相同，按这个规则比就够了。注意要返回的是重排后的 S，不是 finalS。

原帖的描述不完整，这篇是这样处理的：

• 原帖没有给样例，也没有给数据范围，真题的数据范围未核实。下面「测试用例」一节里的例子都是自己算出来的。
• 原帖前后用的变量名不一致，这里把 S 和 shipmentData、finalS 和 finalSequence 各当作同一个东西，统一写成 S 和 finalS。
• 规则按原帖的字面意思理解：每一步都是先追加、再反转，所以最后一个字符追加完之后也要再反转一次【推断：原帖只有这一句规则，没有样例能核对】。

举个例子，S = "0101" 时，finalS 的变化过程如下（每一步先写追加后的结果，再写反转后的结果；只有一个字符时反转后不变）："0" → "01" 反转成 "10" → "100" 反转成 "001" → "0011" 反转成 "1100"。

面经里怎么考的

这道题来自 2026-01 下旬【推断：帖子只显示 01-24，年份按站点显示规则推断】的一篇 OA 面经。帖子是匿名发在论坛英文区的，岗位和身份都没写。这次 OA 一共两道编程题，帖子里只描述了这一道，没说是第几题，也没写时长和用的平台。发帖人没有通过全部测试用例（test case），发帖是为了求解法，还说自己刷了很多 LeetCode 题，也没见过这类题。

从这篇面经能得到的教训是：这道题要先模拟过程、再从中找规律，属于构造题（constructive problem，要求构造出一个满足条件的答案），不在常见的题型清单里，硬套熟悉的模板是套不上的。考场上应该先用 c1 c2 c3 c4 c5 这样的符号代替具体字符，手推四五步，看出 finalS 的每个位置固定来自 S 的哪个位置。看出这个对应关系之后，剩下的就是先确定字典序最大的 finalS 长什么样（见「思路」一节），再按这个对应关系把它的每个字符填回 S 里对应的下标，扫一遍就能完成。

发帖人没写自己具体卡在哪里。【推断】比较容易丢分的地方有两处：一是每一步都真的把字符串反转一遍，总共是 O(n²)，数据规模大时会超时；二是漏掉最后一次反转，或者把 n 为奇数和偶数时的规律弄反，这样会有一部分测试用例的答案出错。按发帖人的描述，这题用 O(n) 的做法几行代码就能写完。不过真题是否还有发帖人没写出来的限制条件，未核实；考场上如果题面和这里写的不一样，以题面为准。

思路

下面记 S 的长度为 n，用 c_i 表示 S 从左往右数的第 i 个字符。

1. 反转只改变字符的位置，不看字符是什么，所以整个过程相当于对位置做一次固定的置换（permutation）。 也就是说，finalS 的每一位来自 S 的哪个下标，只和长度 n 有关，和 S 的内容无关。用符号推几步就能看出来（每行是那一步反转之后的结果）：

第 1 步：c1
第 2 步：c2 c1
第 3 步：c3 c1 c2
第 4 步：c4 c2 c1 c3
第 5 步：c5 c3 c1 c2 c4

从中可以看出规律，finalS 由两段拼成，下文就叫它们第一段（降序）和第二段（升序）。第一段从 c_n 开始，每次隔一个往前取（c_n, c_{n-2}, c_{n-4}, …），一直取到开头；第二段取剩下的、和 n 奇偶性不同的那些下标，从其中最小的开始，每次隔一个往后取（…, c_{n-3}, c_{n-1}）。换成从 0 开始的下标来写：finalS 的第 0, 1, 2, … 位依次来自 S 的下标 n-1, n-3, n-5, …（第一段），接着是 n%2, n%2+2, …, n-2（第二段）。

2. 既然位置之间的对应关系是固定的，重排 S 就等于直接重排 finalS，finalS 可以是这些字符的任意一种排列。 字典序是从前往后逐位比较的，所以把大的字符尽量往前放，得到的串最大，也就是所有 1 在前、0 在后：'1' * ones + '0' * zeros（ones 和 zeros 是 S 里两种字符各自的个数）。
3. 再把 finalS 反推回 S。 finalS 前 ones 位分别来自 S 的哪些下标，就在 S 的这些下标上放 1，其余位置放 0。因为置换是一一对应（bijection）的，finalS 确定了，S 也就唯一确定了，所以满足条件的 S 只有一个，不存在几个答案并列、还要再挑一个的问题。这一点也实际验证过：用一个写法简单、不容易错但很慢的暴力解（brute force），在大量小数据上和正式解法逐个比对结果（这种做法叫对拍），逐组确认了最优解唯一，用了哪些数据见「代码」一节。
4. 考场上记不住这个规律也没关系，可以直接模拟一遍：对下标 0..n-1 按同样的规则跑一次，得到的下标顺序就是这个置换，见代码里的 max_final_arrangement_sim。模拟时用双端队列（deque）加一个「当前是否处于反向状态」的标记：反转时不真的把队列翻过来，只把标记取反；追加时根据标记决定加在队列的哪一端。这样每一步都只要常数时间。

代码

代码已运行，下面 __main__ 里的用例全部通过。另外还和暴力解做了对拍（什么是对拍见「思路」一节）。暴力解的做法是枚举 1 的所有摆法，每一步都真的拼接再反转。比对的数据包括：n ≤ 8 的全部 0/1 串（511 个）逐个枚举，再加 500 组 n ≤ 12 的随机串，结果都一致，而且每一组的最优解都是唯一的。规模大的数据上没有跑暴力解，只比对了两种正式写法：在 50 组 n ≤ 2×10^5 的随机串上，max_final_arrangement 和 max_final_arrangement_sim 的结果一致，用 build_final 校验，得到的 finalS 都是 1...10...0。

from collections import deque


def build_final(s):
    """按题意模拟：每个字符先追加到末尾，再整体反转。翻转只翻标记，O(n)。"""
    dq, flipped = deque(), False  # flipped 为 True 时，dq 存的是逻辑串的反向
    for c in s:
        if flipped:
            dq.appendleft(c)  # 逻辑末尾此时在 dq 左边
        else:
            dq.append(c)
        flipped = not flipped
    res = ''.join(dq)
    return res[::-1] if flipped else res


def max_final_arrangement(s):
    """返回重排后的 S，使 build_final(S) 字典序最大。O(n)。"""
    n, ones = len(s), s.count('1')
    # finalS 第 0, 1, 2, ... 位依次来自 S 的下标 n-1, n-3, ...（降序），
    # 然后是另一奇偶的下标从小到大（升序）。
    order = list(range(n - 1, -1, -2)) + list(range(n % 2, n - 1, 2))
    res = ['0'] * n
    for i in order[:ones]:  # 最优 finalS = 1...10...0，前 ones 位对应的下标放 1
        res[i] = '1'
    return ''.join(res)


def max_final_arrangement_sim(s):
    """记不住规律时的写法：对下标 0..n-1 跑一遍同样的过程，直接得到置换。"""
    n = len(s)
    dq, flipped = deque(), False
    for i in range(n):
        if flipped:
            dq.appendleft(i)
        else:
            dq.append(i)
        flipped = not flipped
    order = list(dq)[::-1] if flipped else list(dq)  # order[j]：finalS 第 j 位来自 S 的哪个下标
    res = ['0'] * n
    for i in order[:s.count('1')]:
        res[i] = '1'
    return ''.join(res)


if __name__ == '__main__':
    cases = [
        ('0011', '0101'),
        ('10', '01'),
        ('1', '1'),
        ('000', '000'),
        ('111', '111'),
        ('10101', '10101'),
        ('110100', '010101'),
        ('', ''),
    ]
    for s, want in cases:
        got = max_final_arrangement(s)
        assert got == want == max_final_arrangement_sim(s), (s, got, want)
        k = s.count('1')
        assert build_final(got) == '1' * k + '0' * (len(s) - k)
    print('all passed')

复杂度

时间 O(n)，空间 O(n)。build_final 用双端队列加反向标记来模拟，每一步只在队列的一端加一个字符、再把标记取反，都是常数时间，所以整体也是 O(n)。如果每一步都真的写 f = (f + c)[::-1]，每次都要把当前整个字符串复制并反转一遍，长度最多到 n，总共就是 O(n²)。

易错点

• 要返回的是重排后的 S，不是 finalS。最优情况下的 finalS 永远是 1...10...0 这种形式，直接返回它是错的。
• 最后一个字符追加完之后还要再反转一次。漏掉这一步，就等于用了下面 Follow-up 里「先反转再追加」的规则，第一段和第二段的奇偶正好整个对调："0011" 会算出 "1010"，而正确答案是 "0101"。
• 第二段从哪个下标开始，由 n 的奇偶决定。代码里先用 range(n - 1, -1, -2) 降序走完第一段，它永远从 n-1 起步，最后停在 0 还是 1 取决于 n 的奇偶；再用 range(n % 2, n - 1, 2) 升序走第二段。写完以后把 n = 1、n = 2 代进去自己核对一下。
• 不要枚举所有排列，也不要用「逐位贪心（greedy）+ 每次重新模拟」的办法。这些做法要么要试 C(n, ones) 种摆法（从 n 个位置里选出 ones 个位置的方法数），要么要做 O(n²) 的模拟，数据规模一大都会超时。
• 空串、全是 0、全是 1 这几种边界情况，上面的写法会原样返回输入，不需要单独处理。

测试用例

原帖没有样例，下面是自己算的，每一行都在代码的 __main__ 里用 assert 检查过：

Follow-up

• 如果只问最大的 finalS 是什么，就不用反推 S 了，直接返回 '1' * ones + '0' * zeros。
• 如果规则换成「先反转再追加」（这和本题漏掉最后一次反转是等价的），整个过程仍然是一个固定的置换，只要把 max_final_arrangement_sim 循环里「追加」和「把标记取反」这两步对调就行。这时 "0011" 的答案变成 "1010"。这个变体也单独和暴力解对拍过 400 组，结果一致。
• 如果字符不止 0 和 1（比如可以是任意小写字母），思路不变：最大的 finalS 就是把所有字符按降序排好，再按同一个置换，把第 j 大的字符放到 order[j] 这个下标上（order[j] 是 finalS 第 j 位对应的 S 下标，见代码）。这个变体和暴力解（n ≤ 7，字母表只用 abc）对拍过 300 组，结果一致，而且最优解唯一。

英文讲法

向面试官解释思路时可以这样说，其中置换（permutation）和一一对应（bijection）是关键词：

Appending and then reversing never looks at the characters, so the whole process is just a fixed permutation of positions. Tracing a few steps shows the final string takes the last index, then every second index going left, then the remaining indices going right. Since any arrangement of the final string is reachable, the best one is all ones followed by all zeros, and I just map those positions back to indices in the original string. That's linear time, and the answer is unique because the permutation is a bijection.