寻找最小误差的回文字符串：现有代码仅支持短长度，求通用解法

给定一个字符串数组，每个字符串长度均为m。两个字符串s1和s2的误差定义为对应位置字符在英文字母表中绝对距离的总和。需要找到一个长度为m的字典序最小的回文字符串alpha，使得该字符串与数组中所有字符串的误差总和最小。

示例 #

输入：

array = ["aa","yy","mm"]

输出：

mm

约束条件 #

1 <= n * m <= 2 * 10^5
仅使用小写英文字母

我的代码及问题 #

我写的代码仅能在输入字符串长度为2或3时正确运行，无法处理长度大于3的情况，请求帮助：

static String solve(List<String> list) {
    int n = list.size();
    int m = list.get(0).length();
    StringBuilder sb = new StringBuilder();
    sb.append('a');
    for(int i=1; i<m-1; i++) sb.append('b');
    sb.append('a');

    int diff = Integer.MAX_VALUE;
    String resp = sb.toString();
    char[] ar = resp.toCharArray();
    for(char k='a'; k<='z'; k++) {
        ar[0] = k;
        ar[ar.length-1]=k;
        int d = 0;
        for(int i=0; i<n; i++) {
            String msg = list.get(i);
            for(int j=0; j<m; j++) {
                int e1 = msg.charAt(j) - 'a';
                int e2 = ar[j] - 'a';
                d += Math.abs(e1 - e2);
            }
        }
        if(diff > d) {
            diff = d;
            resp = new String(ar);
        }
    }
    return resp;
}

解决方案 #

你的代码只固定处理了首尾位置，中间字符硬编码为'b'，忽略了回文字符串的核心规则：对称位置的字符必须相同，比如第j位和第m-1-j位的字符要一致。正确的处理逻辑应该是按对称位置分组，每组单独计算最优字符。

核心思路 #

1. 对称分组：将字符串的位置按对称关系分组，比如长度为m的字符串中，第j位和第m-1-j位为一组（当j <= m-1-j时）；如果是奇数长度的中间位，单独作为一组。
2. 计算每组最优字符：对每组，统计所有输入字符串对应位置的字符频次，遍历所有小写字母，找到能使该组所有字符到它的距离总和最小的字符；若多个字符总和相同，选字典序最小的那个。
3. 填充结果：将每组确定的字符填入对应的对称位置，得到最终的回文字符串。

修正后的代码 #

import java.util.List;

public class Solution {
    static String solve(List<String> list) {
        if (list.isEmpty()) return "";
        int n = list.size();
        int m = list.get(0).length();
        char[] result = new char[m];

        // 遍历每一组对称位置
        for (int j = 0; j <= (m - 1) / 2; j++) {
            int mirrorJ = m - 1 - j;
            int[] charCount = new int[26];
            int total = 0;

            // 统计该组所有字符的频次
            for (String s : list) {
                charCount[s.charAt(j) - 'a']++;
                total++;
                if (j != mirrorJ) {
                    charCount[s.charAt(mirrorJ) - 'a']++;
                    total++;
                }
            }

            // 找到距离总和最小、字典序最小的字符
            int minDistanceSum = Integer.MAX_VALUE;
            char bestChar = 'a';
            for (char c = 'a'; c <= 'z'; c++) {
                int currentIdx = c - 'a';
                int sum = 0;
                for (int i = 0; i < 26; i++) {
                    sum += charCount[i] * Math.abs(i - currentIdx);
                }
                // 更新最优解：总和更小，或总和相同但字典序更小
                if (sum < minDistanceSum || (sum == minDistanceSum && c < bestChar)) {
                    minDistanceSum = sum;
                    bestChar = c;
                }
            }

            // 填充对称位置
            result[j] = bestChar;
            result[mirrorJ] = bestChar;
        }

        return new String(result);
    }
}

代码说明 #

• 按对称位置分组处理，严格保证回文结构。
• 统计每组字符频次后，遍历所有小写字母计算距离总和，确保找到符合要求的最优字符。
• 时间复杂度为O((m/2)2626 + nm)，其中26是常数，完全满足nm<=2e5的性能约束。

内容的提问来源于stack exchange，提问作者Learner