题目与场景
每次相邻交换成本为 1，字符可能重复，也可能因多个奇数频次而无法组成回文。目标是最少交换，不是任意构造一个回文。
面试官考察什么
- 推导奇数频次可行性条件。
- 从右侧为左端字符选择最近可用匹配。
- 证明贪心最优，并正确计算移动成本。
作答前的澄清问题
- 只能相邻交换且每次成本为 1 吗？
- 字符集是否任意，Unicode 码点是否视为字符？
- 函数可以修改数组，还是只返回计数？
- 输入规模是否允许 O(n²)？
30 秒回答框架
先统计奇数频次；超过 1 次就无法组成回文。使用两端指针，端点相等时向内收缩；不等时从右边界向左寻找左端字符，把它通过相邻交换冒泡到右端并累计移动次数。找不到匹配时，该字符必须是唯一中心，将它一步步移向中间。
分步深挖
1. 证明可行性
回文的对称位置成对出现，最多只有奇数长度的中心可以单独存在，因此奇数频次最多 1 个。先检查可避免在不可行输入上执行贪心。
2. 匹配边界
对指针 i、j，若 s[i] 等于 s[j]，两端都已固定。否则从 j 向 i + 1 搜索 s[k] == s[i]。把该字符移到右端需要 j - k 次交换，且不会破坏已固定前缀。
3. 处理中心字符
找不到匹配时，s[i] 就是应放在中心的奇数频次字符。每次向右交换一步，直到到达中间并计数。不能丢弃它，也不能假设第一轮就能直接找到中心。
4. 实现模拟
text
统计奇数频次
若 odd_count > 1：返回不可行
left = 0，right = n - 1，swaps = 0
当 left < right：
若 s[left] == s[right]：left 加一，right 减一，继续
k = right
当 k > left 且 s[k] != s[left]：k 减一
若 k == left：交换 s[k] 与 s[k + 1]，swaps 加一
否则：将 s[k] 冒泡到 right，累计每次相邻交换
left 加一，right 减一
返回 swaps5. 分析复杂度与证明思路
每轮搜索和冒泡最多 O(n)，共 O(n) 轮，因此时间 O(n²)，可变数组外额外空间 O(1)。最近的匹配字符移动成本最低；更远匹配至少需要同样多的相邻交换。中心情况由奇数频次唯一性决定。
高质量示范回答
“先统计奇数频次，超过 1 个就返回不可行。然后比较两端；不匹配时寻找靠近右边界的相同字符并冒泡到位，加入移动距离；若找不到，它就是唯一奇数中心，就向中间移动。端点匹配后收缩窗口。模拟为 O(n²) 时间、O(1) 额外空间，最近匹配最优，因为更远字符需要至少同样多的相邻交换。”
常见误区
- 要求所有频次都为偶数 → 奇数长度允许一个奇数频次 → 最多允许一个。
- 随便选匹配字符 → 移动可能不是最少 → 选靠近边界的匹配。
- 丢掉找不到匹配的字符 → 少算中心移动 → 把它冒泡到中间。
- 双指针直接交换不移动中间元素 → 丢失相邻交换成本 → 模拟每次相邻移动或使用等价数据结构。
追问与回答
能同时返回最终回文吗？
可以。保留可变数组并返回最终内容与计数；如需交换序列，可记录每次相邻交换。
大输入如何优化？
用 Fenwick 树或顺序统计结构维护原始位置，让移动成本在对数时间更新。贪心配对不变，只避免逐元素移动。
如果允许任意位置交换呢？
成本模型不同，最近匹配的距离证明不再适用。先明确操作规则，再设计新算法。