在字符串处理算法中，有一道经典高频面试题：给定一个字符串，允许在任意位置添加字符，要求计算最少添加多少个字符能使整个字符串成为回文串，并输出其中一种合法结果。这道题本身就具备一定挑战性，而其进阶版本额外引入了最长回文子序列字符串（strlps），目标是在已知该子序列的前提下进一步降低时间复杂度。本文将详细拆解这道进阶问题的解法，帮助读者深入理解“剥洋葱”式的高效思路。
题目与进阶要求
原问题：给定一个字符串str，返回在添加字符最少的情况下，使str整体成为回文字符串的任意一种结果。
进阶问题：额外提供str的最长回文子序列字符串strlps，要求设计一种比原问题时间复杂度更低的算法。
该题难度标记为“困难”，但一旦掌握核心思路，就会发现它其实是一个层层剥离的“剥洋葱”过程，直观且高效，适合在面试或竞赛中快速实现。
解题思路详解
如果已拥有最长回文子序列字符串strlps，算法时间复杂度可优化至O(N)。设str长度为N，strlps长度为M，最终回文串的总长度为2×N − M。解法类似于逐层剥洋葱：每次处理当前最外层的一对字符，并填充到结果数组的两端。
以下通过具体例子演示完整步骤：
str = "A1BC22DE1F"，strlps = "1221"。首先创建结果数组res，长度为2×N − M。
洋葱的第0层由strlps[0]和strlps[M-1]组成，即"1...1"。从str最左侧开始查找字符'1'，发现字符'A'位于str第0位，'1'位于第1位，因此左侧第0层洋葱圈外的部分为"A"，记作leftPart。从str最右侧开始查找字符'1'，右侧第0层洋葱圈外的部分为"F"，记作rightPart。将(leftPart + rightPart的逆序)复制到res左侧未赋值的位置，将(rightPart + leftPart逆序)复制到res右侧未赋值的位置，此时res变为"AF..FA"。然后将洋葱的第0层"1"复制到res左右两侧未赋值的位置，res变成"AF1..1FA"。至此，第0层被剥离。
洋葱的第1层由strlps[1]和strlps[M-2]组成，即"2...2"。从str左侧第0层洋葱向右查找'2'，发现左侧第1层洋葱圈外的部分为"BC"，记作leftPart。从str右侧第0层洋葱向左查找'2'，右侧第1层洋葱圈外的部分为"DE"，记作rightPart。同样操作：将(leftPart + rightPart逆序)复制到res左侧，将(rightPart + leftPart逆序)复制到res右侧，res变为"AF1BCED..DECB1FA"。然后复制第1层"2"，res变成"AF1BCED2..2DECB1FA"。第1层剥离完毕，洋葱被完全剥开，最终结果"AF1BCED22DECB1FA"。
整个流程的核心是不断定位当前洋葱层的左、右外部分，将(leftPart + rightPart逆序)填入res左侧，将(rightPart + leftPart逆序)填入res右侧，直至所有洋葱层处理完毕。理解这一逻辑后，代码实现便水到渠成。
完整代码实现（Java）
package live.every.day.ProgrammingDesign.CodingInterviewGuide.String;
/**
* 添加最少字符使字符串整体变成回文串
*
* 【原题】
* 给定字符串str，可在任意位置添加字符，返回添加字符最少的情况下使str整体为回文串的一种结果。
*
* 【进阶题】
* 给定str及其最长回文子序列字符串strlps，返回添加最少字符使str整体为回文串的一种结果。
* 进阶问题多了一个参数，要求时间复杂度低于原问题的实现。
*
* 【难度】
* 困难
*
* 【解答】
* 进阶问题解法。
*
* 已知strlps后，时间复杂度可降至O(N)。设str长度为N，strlps长度为M，最终回文串长度为2×N - M。
* 本解法采用“剥洋葱”思想，下面通过示例说明：
*
* str="A1BC22DE1F"，strlps="1221"。res长度为2×N - M。
* 洋葱第0层由strlps[0]和strlps[M-1]组成，即"1...1"。从str最左侧找'1'，发现'A'是str[0]，'1'是str[1]，
* 因此左侧第0层外部分为"A"，记为leftPart。从str最右侧找'1'，右侧第0层外部分为"F"，记为rightPart。
* 将(leftPart+rightPart逆序)复制到res左侧，将(rightPart+leftPart逆序)复制到res右侧，res变为"AF..FA"。
* 再将洋葱第0层复制到res左右两侧，res变为"AF1..1FA"。第0层剥离完毕。
* 洋葱第1层由strlps[1]和strlps[M-2]组成，即"2...2"。从str左侧第0层向右找'2'，左侧第1层外部分为"BC"，记为leftPart。
* 从str右侧第0层向左找'2'，右侧第1层外部分为"DE"，记为rightPart。
* 将(leftPart+rightPart逆序)复制到res左侧，将(rightPart+leftPart逆序)复制到res右侧，res变为"AF1BCED..DECB1FA"。
* 再将洋葱第1层复制到res左右两侧，res变为"AF1BCED2..2DECB1FA"。第1层剥离完毕，洋葱剥完，返回"AF1BCED22DECB1FA"。
*
* 整个过程反复寻找洋葱圈的左、右外部分，将(leftPart+rightPart逆序)填入res左侧，将(rightPart+leftPart逆序)填入res右侧，
* 直至所有层处理完成。具体实现参见下方getPalindrome2方法。
*
* @author Created by LiveEveryDay
*/
public class AddMinCharsMakePalindrome2 {
public static String getPalindrome2(String str, String strlps) {
if (str == null || str.equals("")) {
return "";
}
char[] chas = str.toCharArray();
char[] lps = strlps.toCharArray();
char[] res = new char[2 * chas.length - lps.length];
int chasLeft = 0;
int chasRight = chas.length - 1;
int lpsLeft = 0;
int lpsRight = lps.length - 1;
int resLeft = 0;
int resRight = res.length - 1;
int tmpLeft = 0;
int tmpRight = 0;
while (lpsLeft <= lpsRight) {
tmpLeft = chasLeft;
tmpRight = chasRight;
while (chas[chasLeft] != lps[lpsLeft]) {
chasLeft++;
}
while (chas[chasRight] != lps[lpsRight]) {
chasRight--;
}
set(res, resLeft, resRight, chas, tmpLeft, chasLeft, chasRight, tmpRight);
resLeft += chasLeft - tmpLeft + tmpRight - chasRight;
resRight -= chasLeft - tmpLeft + tmpRight - chasRight;
res[resLeft++] = chas[chasLeft++];
res[resRight--] = chas[chasRight--];
lpsLeft++;
lpsRight--;
}
return String.valueOf(res);
}
private static void set(char[] res, int resl, int resr, char[] chas, int ls, int le, int rs, int re) {
for (int i = ls; i < le; i++) {
res[resl++] = chas[i];
res[resr--] = chas[i];
}
for (int i = re; i > rs; i--) {
res[resl++] = chas[i];
res[resr--] = chas[i];
}
}
public static void main(String[] args) {
String str = "A1B21C";
String strlps = "121";
System.out.printf("The palindrome is: %s", getPalindrome2(str, strlps));
}
}
// ------ 输出结果 ------
/*
The palindrome is: AC1B2B1CA
*/
