LeetCode移除相邻重复字符：C++循环为何无法完整执行？

问题背景 #

这是LeetCode的「移除所有相邻重复字符」题目，我尝试用非栈思路写C++代码，但运行时循环没法完整执行，还出现报错。

原代码：

class Solution {
public:
    string removeDuplicates(string s) {
        
        for (int i = 0; i < s.length(); i++) {
            if(s[i] == s[i+1]){
                s.erase(i,2);
                i=0;
            }
            
        }
        
        return s;
    }
};

报错原因是数组越界访问——当i走到字符串最后一个字符的索引时，i+1超出了字符串的有效下标范围，访问s[i+1]属于非法内存操作，直接触发报错。

核心问题拆解 #

1. 越界漏洞：循环条件i < s.length()允许i取到s.length()-1，此时i+1等于字符串长度，而字符串的下标只能到s.length()-1，这时候访问s[i+1]必然越界。
2. 低效的重置逻辑：每次删除后把i重置为0，虽然能重新扫描前面的字符，但会导致大量重复遍历，效率极低；而且这种方式本质上没解决越界问题，只要循环走到最后一个字符，还是会触发报错。

修正后的代码 #

调整循环逻辑，避免越界，同时删除后回退索引而非重置：

class Solution {
public:
    string removeDuplicates(string s) {
        int i = 0;
        // 循环条件保证i+1不会越界
        while (i < (int)s.size() - 1) {
            if (s[i] == s[i+1]) {
                s.erase(i, 2);
                // 删除后回退i，防止前面的字符和当前位置形成新重复
                if (i > 0) {
                    i--;
                }
            } else {
                i++;
            }
        }
        return s;
    }
};

关键修正点 #

• 把循环条件改成i < s.size() - 1，确保i+1始终是有效下标，从根源避免越界。
• 删除重复后，如果i大于0就回退一位，比如处理"aabb"时，删除前两个a后变成"bb"，回退i到0就能立刻检测到新的相邻重复。
• 只有没找到重复时才递增i，保证每个位置都被正确检查。

更高效的双指针实现（非栈） #

如果想进一步提升效率，可以用双指针法，避免频繁调用erase（erase操作时间复杂度较高）：

class Solution {
public:
    string removeDuplicates(string s) {
        int j = 0;
        for (int i = 0; i < s.size(); i++) {
            // 模拟栈：如果当前字符和前一个保留的字符相同，就回退指针
            if (j > 0 && s[j-1] == s[i]) {
                j--;
            } else {
                // 否则保留当前字符
                s[j++] = s[i];
            }
        }
        // 截断字符串到有效长度
        s.resize(j);
        return s;
    }
};

这种方法时间复杂度O(n)，空间复杂度O(1)（原地修改），比频繁删除的版本高效得多。

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