本文深入剖析使用栈判断字符串是否可重排为回文串时的经典逻辑错误，指出其导致假阳性（如 "cabcc"）和假阴性（如 "acac"）的根本原因，并提供基于字符频次统计的高效、可靠解决方案。
本文深入剖析使用栈判断字符串是否可重排为回文串时的经典逻辑错误，指出其导致假阳性（如 "cabcc"）和假阴性（如 "acac"）的根本原因，并提供基于字符频次统计的高效、可靠解决方案。
在解决“判断字符串能否重排构成回文串”这一经典问题时，直觉上可能尝试用栈模拟“配对消除”——每遇到一个新字符就入栈，若已存在则出栈，最后检查栈中剩余元素是否 ≤1。但这种思路本质上是错误的，因为它错误地将“后进先出（LIFO）”的栈结构用于处理无序配对问题，而字符配对本身与顺序无关。
❌ 栈方法为何失败？两个关键反例
假阳性（False Positive）：输入
"cabcc"
执行过程：c→a→b→c（此时栈为[c,a,b]，遇到第二个c，stack.contains('c')为true，于是pop()→ 移除栈顶b？错！实际上Stack.contains()查的是是否存在该元素，但pop()永远只弹出栈顶（最后入栈）元素。因此真实行为是：c入栈 →[c]a入栈 →[c,a]b入栈 →[c,a,b]
第二个c：contains('c') == true→pop()→ 弹出b→[c,a]
第三个c：contains('c') == true→pop()→ 弹出a→[c]
最终栈大小为 1，返回true—— 但"cabcc"字符频次为{a:1, b:1, c:3}，有3 个奇数频次字符，不可能构成回文（回文最多允许 1 个奇频字符）。❌假阴性（False Negative）：输入
"acac"
频次{a:2, c:2}，全为偶数，显然可构成"acca"或"caac"。
但栈行为：a→c→a（contains('a')为true，pop()弹出c）→[a]→c入栈 →[a,c]，栈大小为 2，返回false。❌
问题核心：stack.contains()破坏了配对的语义——它不保证弹出的是同一个字符的前一次出现，而只是任意一个匹配项；且pop()的 LIFO 特性使配对完全脱离字符实际分布。
✅ 正确解法：频次统计（哈希表）
回文串重排的充要条件是：至多一个字符的出现次数为奇数，其余字符出现次数必须为偶数。
因此，只需统计每个字符频次，再统计奇数频次字符的个数即可。
import java.util.HashMap;
import java.util.Map;
boolean solution(String inputString) {
Map<Character, Integer> freq = new HashMap<>();
// 统计每个字符出现次数
for (char c : inputString.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
// 统计奇数频次字符的个数
int oddCount = 0;
for (int count : freq.values()) {
if (count % 2 == 1) {
oddCount++;
}
}
// 最多允许 1 个奇频字符
return oddCount <= 1;
}✅ 时间复杂度：O(n)，空间复杂度：O(k)（k 为不同字符数，通常 ≤ 26 或 128）。
✅ 逻辑清晰、无歧义、覆盖所有边界情况（空字符串、单字符、全相同字符等）。
? 进阶优化（空间友好版）
若只关心奇偶性，可用 boolean[] 或位运算进一步优化（例如用 long 的 64 位模拟小写字母奇偶状态），但哈希表方案已足够通用、可读性强，推荐作为标准解法。
总结：算法设计需紧扣问题本质。本题核心是字符数量的奇偶性约束，而非顺序操作，因此应摒弃不匹配的数据结构（如栈），选择能准确建模频次关系的哈希表。理解“为什么错”比“怎么改”更重要——它帮你避开同类陷阱。
