构造最小误差回文串：基于中位数的最优字符选择策略-java教程-PHP中文网

构造最小误差回文串：基于中位数的最优字符选择策略

给定一组等长字符串，需构造字典序最小的回文串，使其与所有输入串的“字母距离和”（即逐位 ascii 差绝对值之和）最小；关键在于对称位置应独立选取使总误差最小的字符——该字符即为对应位置所有字符（含镜像位）的中位数。

给定一组等长字符串，需构造字典序最小的回文串，使其与所有输入串的“字母距离和”（即逐位 ascii 差绝对值之和）最小；关键在于对称位置应独立选取使总误差最小的字符——该字符即为对应位置所有字符（含镜像位）的中位数。

本题本质是多目标优化下的回文约束建模：回文结构强制位置 i 与 m−1−i 字符相等，因此我们只需独立确定前 ⌈m/2⌉ 个位置的字符，后半部分由回文性自动确定。而每个位置的最优字符选择，与其它位置完全解耦——这是本题可高效求解的核心前提。

为什么是中位数？
考虑单一位点 i（及其镜像位 j = m−1−i），设所有 n 个字符串在该位（含镜像位）共提供 2n 个字符（若 i == j，即 m 为奇数且 i 为中位索引，则仅计 n 个）。将这些字符映射为数字 0–25（'a'→0, ..., 'z'→25），则选择目标字符 x ∈ [0,25] 所产生的总误差为：
$$ \text{cost}(x) = \sum_{c \in \text{chars}} |x - c| $$
经典结论指出：使绝对偏差和最小的 x 是这组数的中位数（当总数为偶数时，任意两个中间数之间的整数均可取最小值；为保证字典序最小，我们取最小可行中位数，即下中位数）。

✅ 注意：中位数在此处指数值中位数，而非字符频次中位数。但因字符集离散且有序（a–z），我们可通过频次数组累加快速定位——即找到最小的 k，使得前 k+1 个字母（0 到 k）的累计出现次数 ≥ 总样本数的一半（向上取整）。

以下是完整、正确且高效的 Java 实现：

static String solve(List<string> list) {
    int n = list.size();
    int m = list.get(0).length();
    StringBuilder sb = new StringBuilder();
    int halfLen = (m + 1) / 2; // 前半段长度（含中心）

    for (int i = 0; i = medianTarget) {
                bestChar = c;
                break;
            }
        }
        sb.append((char)('a' + bestChar));
    }

    // 构造完整回文：前半段 + 反转后的前半段（跳过中心字符，若长度为奇数）
    String left = sb.toString();
    String right = new StringBuilder(left).reverse().substring(m % 2);
    return left + right;
}</string>

关键细节说明：

字典序最小保障：我们在中位数候选中自然选取最小满足累计频次条件的字符（break 在首次达标时触发），这恰好对应下中位数，也是所有最小误差解中字典序最小者。
边界处理严谨：halfLen = (m + 1) / 2 正确覆盖奇偶长度；substring(m % 2) 自动跳过中心字符（当 m 为奇数时，m%2==1，截取从索引 1 开始，即舍弃反转后的首字符）。
时间复杂度：O(n × m + 26 × m/2) = O(n × m)，满足约束 n × m ≤ 2×10⁵。