寻找Java中性能更优的字符串替换方案，用于移除指定相邻字母组合

原实现存在的问题 #

你当前使用的循环replace方案最坏时间复杂度为O(n²)：每次replace操作都要全量遍历字符串，还会生成新的字符串对象，遇到长字符串、嵌套匹配场景时会产生大量无效遍历和对象创建开销，性能损耗严重。

最优实现思路：栈遍历（时间复杂度O(n)） #

仅需一次遍历即可完成全部匹配移除操作，核心逻辑如下：

• 用StringBuilder模拟栈结构，无需额外转换即可直接生成最终结果
• 逐个遍历输入字符串的每个字符：
  • 若栈为空，直接将当前字符压入栈
  • 若栈不为空，取栈顶字符与当前字符配对，判断是否属于要移除的组合（AB/BA/CD/DC）
  • 配对成功则弹出栈顶字符，跳过当前字符的压入操作
  • 配对失败则将当前字符压入栈
• 遍历完成后，栈中剩余内容就是最终输出结果

逻辑验证（对应示例2：输入CABABD） #

1. 栈为空，压入C → 栈内容：[C]
2. 下一个字符为A，栈顶C配对CA不匹配，压入A → 栈内容：[C,A]
3. 下一个字符为B，栈顶A配对AB匹配，弹出A → 栈内容：[C]
4. 下一个字符为A，栈顶C配对CA不匹配，压入A → 栈内容：[C,A]
5. 下一个字符为B，栈顶A配对AB匹配，弹出A → 栈内容：[C]
6. 下一个字符为D，栈顶C配对CD匹配，弹出C → 栈为空，最终输出空字符串，和示例结果一致

优化后代码实现 #

public String transformString(String s) {
    StringBuilder stack = new StringBuilder();
    for (char current : s.toCharArray()) {
        int stackSize = stack.length();
        if (stackSize > 0) {
            char top = stack.charAt(stackSize - 1);
            // 直接判断是否属于可移除组合，比HashSet查找性能更高
            if ((top == 'A' && current == 'B') || (top == 'B' && current == 'A')
                    || (top == 'C' && current == 'D') || (top == 'D' && current == 'C')) {
                stack.deleteCharAt(stackSize - 1);
                continue;
            }
        }
        stack.append(current);
    }
    return stack.toString();
}

该实现仅需一次遍历，没有多余的字符串复制操作，性能比原实现提升数倍到数十倍，字符串越长优势越明显。

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