深入解析：如何高效删除字符串中所有相邻的 k 个重复项

2026-02-07 11:52:27 0条评论 2次阅读 0人点赞

在这篇文章中，我们将深入探讨一个非常经典且富有挑战性的算法问题：如何从一个字符串中反复删除所有相邻的 k 个重复项，直到无法再删除为止。这个问题不仅能帮助我们深入理解栈这种数据结构的强大之处，还能让我们学会如何处理复杂的字符串匹配逻辑。

我们会一起分析问题的核心难点，设计出高效的解决方案，并通过详细的代码实现和实际案例，让你彻底掌握这一技巧。无论你是在准备面试，还是想要提升自己的算法思维能力，这篇文章都会为你提供实用的见解和指导。

问题陈述与理解

首先，让我们明确一下具体的要求。给定一个字符串 INLINECODE1434809d 和一个整数 INLINECODE56043ec8，我们的任务非常明确：

  • 扫描字符串：我们需要检查字符串中是否存在 k 个连续且相同的字符。
  • 执行删除：如果找到了这样的 k 个字符，就将它们从字符串中完全删除。
  • 连接与重复：删除后，原本位于这 INLINECODEe8fa2c8e 个字符左侧和右侧的部分会“接”在一起。这可能会形成新的相邻重复项，所以我们需要反复执行上述操作，直到字符串中不再存在长度为 INLINECODEc3c1a0f9 的相邻重复项为止。
  • 返回结果：最终剩下的字符串就是我们需要的结果。

#### 让我们来看一个具体的例子：

假设 INLINECODEe542a4c1，INLINECODEf4079da5。

我们可以通过以下步骤来模拟过程：

  • 第一轮扫描：

* 我们发现 INLINECODE16ec7125 是 3 个连续的 INLINECODE0be0e8bc，将其删除。字符串变为 INLINECODEa50efb35（注意，原来的 INLINECODE8914a4fc 被打断了，变成了 d...d）。

* 继续扫描，又发现 INLINECODEb22a94a0，将其删除。字符串变为 INLINECODE77101cac（中间的 INLINECODE41181d16 没了，INLINECODEc293822d 连在了一起）。

  • 第二轮扫描：

* 现在的字符串是 INLINECODE07283c4e（为了方便理解加了空格，实际是 INLINECODE1d43bc8f）。我们发现 INLINECODE9b05fcc4 是 3 个连续的，将其删除。字符串变为 INLINECODE2170c9d4（删除后，两边的 INLINECODE65cf971b 连在了一起，形成了 INLINECODEc153d842）。

  • 第三轮扫描：

* 现在的字符串是 INLINECODE9747d7d9。我们发现 INLINECODE215ecd09 是 3 个连续的，将其删除。字符串变为 "bdaa"。

  • 最终结果：

* 现在 INLINECODEfc0da1b5 中没有 3 个连续的相同字符了（INLINECODE8d663c76 只有 2 个），处理结束，返回 "aa"。

核心解法：利用栈进行计数

解决这个问题最直观的方法是反复扫描字符串并构建新字符串，直到字符串不再变化。这种方法虽然容易想到，但时间复杂度较高，可能达到 O(N^2)，在字符串很长时效率很低。

为了达到线性时间复杂度 O(N)，我们需要一种更聪明的方式来记录和更新字符的连续出现次数。这时，栈 就成了我们的最佳选择。

#### 为什么选择栈？

栈具有“后进先出”（LIFO）的特性，这使得它非常适合处理这类涉及“最近”元素或“相邻”关系的问题。对于本题，我们可以利用栈来跟踪两件事：

  • 字符本身：当前正在处理的字符是什么？
  • 当前计数：该字符在栈顶位置连续出现了多少次？

#### 逐步算法思路

我们将遍历字符串中的每一个字符，并执行以下操作：

  • 初始化：创建一个空栈，用于存储“字符-计数”对（Pair）。
  • 遍历：逐个读取字符串中的字符 c。
  • 检查栈顶：

* 如果栈不为空，且栈顶元素的字符与当前字符 c 相同：

* 这说明我们找到了连续的重复项。我们需要增加栈顶元素的计数。

* 检查是否达到 k：如果增加后的计数等于 INLINECODEb853e4ec，说明这组相邻重复项已经凑齐了 INLINECODEd77aa1bb 个，我们需要将栈顶元素弹出，表示“删除”了这些字符。

* 如果栈为空，或者栈顶元素的字符与当前字符 c 不同：

* 这代表一个新的字符序列开始了。我们将当前字符 INLINECODE9ac9a04c 和计数 INLINECODE53af44c7 作为一个新的元素压入栈中。

  • 构建结果：

* 遍历结束后，栈中剩下的就是所有未被删除的字符及其计数。

* 我们需要按照栈中的顺序（注意：从栈底到栈顶才是正确的字符串顺序），根据每个字符的计数，将它们重复拼接起来，形成最终的结果字符串。

代码实现与详细解析

为了让这个算法更加具体，让我们分别用 C++ 和 Java 来实现它。为了方便你理解，我在代码中添加了详细的中文注释。

#### C++ 实现

在 C++ 中，我们可以使用 INLINECODEb9a4a85f 配合 INLINECODE474f483c 来存储字符和整数。

#include 
#include 
#include 
#include 
#include 

using namespace std;

/*
 * 函数：removeDuplicates
 * 功能：从字符串中删除所有相邻的 k 个重复项
 * 参数：s - 输入的字符串，k - 需要删除的重复项数量
 * 返回值：处理后的最终字符串
 */
string removeDuplicates(string s, int k) {
    // 定义一个栈，用来存储 pair
    // 这里的 pair 会自动处理字符和其计数的关系
    stack<pair> st;

    // 遍历字符串中的每一个字符
    for (char c : s) {
        // 情况1：栈不为空，且当前字符与栈顶字符相同
        if (!st.empty() && st.top().first == c) {
            // 增加栈顶元素的计数
            st.top().second++;
            
            // 关键步骤：如果计数达到了 k，说明这 k 个字符需要被删除
            if (st.top().second == k) {
                st.pop(); // 弹出栈顶，相当于删除了这组字符
            }
        }
        // 情况2：栈为空，或者当前字符与栈顶字符不同
        else {
            // 将新字符压入栈中，计数初始化为 1
            st.push({c, 1});
        }
    }

    // 此时栈中存储的就是无法再删除的字符组合
    // 我们需要构建结果字符串
    string result = "";
    
    // 使用 vector 临时存储，以便正序构建（因为栈弹出是逆序的）
    // 也可以直接在 string 头部插入，但那样效率较低
    vector<pair> tempVec;
    while (!st.empty()) {
        tempVec.push_back(st.top());
        st.pop();
    }
    // 反转 vector 使其恢复正确的字符顺序
    reverse(tempVec.begin(), tempVec.end());

    // 遍历 vector，根据计数拼接字符串
    for (auto p : tempVec) {
        result.append(p.second, p.first);
    }

    return result;
}

int main() {
    // 测试用例 1：没有重复项
    string s1 = "abcd";
    int k1 = 2;
    cout << "输入: " << s1 << ", k=" << k1 << endl;
    cout << "输出: " << removeDuplicates(s1, k1) << endl;
    cout << "----------------------------------" << endl;

    // 测试用例 2：典型的嵌套删除
    string s2 = "deeedbbcccbdaa";
    int k2 = 3;
    cout << "输入: " << s2 << ", k=" << k2 << endl;
    cout << "输出: " << removeDuplicates(s2, k2) << endl;
    cout << "----------------------------------" << endl;

    // 测试用例 3：连续删除导致的新连续项
    string s3 = "pbbcggttciiippooaais";
    int k3 = 2;
    cout << "输入: " << s3 << ", k=" << k3 << endl;
    cout << "输出: " << removeDuplicates(s3, k3) << endl;
    
    return 0;
}

#### Java 实现

在 Java 中，由于 INLINECODE615a05f5 类操作对象比较麻烦，通常推荐使用 INLINECODE6e90da20（双端队列）来实现栈的功能。我们需要定义一个简单的辅助类 INLINECODE0115a883 来存储字符和计数，或者使用两个并行的栈（一个存字符，一个存计数）。这里我们采用定义 INLINECODE18390954 类的方法，逻辑更清晰。

import java.util.*;

public class RemoveDuplicates {

    // 定义一个简单的内部类，用于存储字符及其计数
    static class Pair {
        char character;
        int count;

        Pair(char character, int count) {
            this.character = character;
            this.count = count;
        }
    }

    /*
     * 函数：removeDuplicates
     * 功能：从字符串中删除所有相邻的 k 个重复项
     */
    public static String removeDuplicates(String s, int k) {
        // 使用 ArrayDeque 作为栈，性能通常比 Stack 类更好
        Deque stack = new ArrayDeque();

        for (char c : s.toCharArray()) {
            // 检查栈顶元素是否与当前字符相同
            if (!stack.isEmpty() && stack.peek().character == c) {
                // 如果相同，增加栈顶元素的计数
                stack.peek().count++;
                
                // 如果计数达到 k，则弹出栈顶元素（模拟删除）
                if (stack.peek().count == k) {
                    stack.pop();
                }
            } else {
                // 如果不同或栈为空，压入新的 Pair，计数为 1
                stack.push(new Pair(c, 1));
            }
        }

        // 构建结果字符串
        StringBuilder result = new StringBuilder();
        
        // 注意：弹出栈的顺序是逆序的，所以我们需要先反转或者倒序插入
        // 这里我们使用一个 List 来暂存，以便正序读取
        List tempList = new ArrayList();
        while (!stack.isEmpty()) {
            tempList.add(stack.pop());
        }
        Collections.reverse(tempList);

        for (Pair p : tempList) {
            for (int i = 0; i < p.count; i++) {
                result.append(p.character);
            }
        }

        return result.toString();
    }

    public static void main(String[] args) {
        // 示例 1
        String s1 = "abcd";
        int k1 = 2;
        System.out.println("输入: \"" + s1 + "\", k=" + k1);
        System.out.println("输出: \"" + removeDuplicates(s1, k1) + "\"");
        System.out.println("--------------------------------");

        // 示例 2
        String s2 = "deeedbbcccbdaa";
        int k2 = 3;
        System.out.println("输入: \"" + s2 + "\", k=" + k2);
        System.out.println("输出: \"" + removeDuplicates(s2, k2) + "\"");
        System.out.println("--------------------------------");
        
        // 示例 3：极端情况，全部删除
        String s3 = "aaabbbccc";
        int k3 = 3;
        System.out.println("输入: \"" + s3 + "\", k=" + k3);
        System.out.println("输出: \"" + removeDuplicates(s3, k3) + "\"");
    }
}

复杂度分析与优化建议

#### 时间复杂度分析

  • O(N)：我们只对字符串进行了一次遍历。虽然内部构建结果字符串时有一个循环，但栈中元素的总体数量也是与 N 成正比的，且每个元素最多被处理两次（进栈一次，出栈一次）。因此，整体时间复杂度是线性的 O(N)，其中 N 是字符串的长度。

#### 空间复杂度分析

  • O(N)：在最坏的情况下（例如字符串中没有重复项，或者 k 很大导致无法删除），我们需要将字符串中的每一个字符都压入栈中。因此，空间复杂度为 O(N)。

#### 常见错误与调试技巧

  • 结果字符串顺序错误：这是一个非常容易出错的地方。因为栈是“后进先出”的，如果你直接从栈中弹出元素并拼接，得到的字符串会是倒序的。一定要记得反转或者倒序插入（如上面的 Java 代码所示）。
  • 栈顶元素判空：在访问 INLINECODEe2b82ca0 或 INLINECODE969b73d2 之前，务必检查栈是否为空。直接访问空栈会导致程序崩溃。
  • 忽略 k 的值：在增加计数后，要立即判断是否等于 k，不要等到下一次循环。

#### 优化建议

在 C++ 实现中，如果我们直接利用 INLINECODE476d7276 字符串本身作为一个栈来操作（即使用 INLINECODE6f39d315 的 INLINECODE42b51ab4 和 INLINECODE1f2ee104），可以避免使用额外的 INLINECODE4f1126a6 结构，但这需要我们维护一个额外的整数数组来记录计数，或者使用两个栈。上面的 INLINECODEcb4e7a3f 写法虽然在逻辑上最清晰，但在极高要求的性能场景下，使用两个并行的栈（一个存字符 INLINECODE705bf0b6，一个存计数 INLINECODEe3a6b72f）可能会减少一些对象构造的开销。

总结与实际应用

通过今天的学习，我们不仅解决了“删除所有相邻 k 个重复项”这个问题，更重要的是掌握了“栈 + 计数器”这一强大的组合模式。

这种模式在实际开发中非常有用，例如：

  • 文本编辑器：实现“撤销”功能或语法高亮时的括号匹配。
  • 数据压缩：简单的行程编码算法思想与此类似。
  • 日志分析：过滤掉连续出现的重复错误日志。

希望这篇文章能帮助你更好地理解栈的应用。当你遇到涉及“相邻”、“连续”、“配对”等关键字的问题时，不妨第一时间想一想：能不能用栈来解决？

继续练习，你会发现算法的世界里充满了这样的智慧与乐趣。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/31820.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年