使用递归实现字符串去重 现有代码运行异常求修复方案

你的现有代码仅判断当前首字符与子串去重结果的首字符是否相等，只能过滤连续重复的字符，无法处理间隔出现的重复字符。你给出的测试用例中，第二个a和前面的b不连续，原有逻辑判断首字符a和后续子串处理结果的首字符b不相等，就直接把a拼接回去，才会得到没有去重的结果。

方案思路 #

保留字符首次出现的位置，递归过程中通过辅助参数记录已经出现过的字符，遇到已记录的字符直接跳过，未记录的字符则拼接到结果中并标记为已出现。

实现代码 #

#include <bits/stdc++.h>
using namespace std;

// 内部递归函数：传入当前待处理字符串、已出现字符标记数组
string removeDupHelper(string s, bool exist[]) {
    if (s.empty()) return "";
    char ch = s[0];
    // 当前字符已经出现过，直接递归处理剩余子串
    if (exist[ch - 'a']) {
        return removeDupHelper(s.substr(1), exist);
    }
    // 当前字符未出现，标记为已出现，拼接到递归结果前
    exist[ch - 'a'] = true;
    return ch + removeDupHelper(s.substr(1), exist);
}

// 对外调用接口，和你原函数签名完全一致
string removeDup(string s) {
    bool exist[26] = {false}; // 假设输入为小写字母，如需处理全ASCII字符可将数组长度改为256，索引直接用ch即可
    return removeDupHelper(s, exist);
}

int main() {
    cout << removeDup("abacd") << endl; // 输出为abcd，符合预期
    return 0;
}

逻辑说明 #

该方案时间复杂度为O(n)，n为字符串长度，效率优于每次遍历递归结果判断是否存在的实现，完全满足作业练习的需求。

如果你不想新增辅助函数，也可以用内置的字符串查找方法实现，只是长字符串下效率略低：

string removeDup(string s) {
    if (s.empty()) return "";
    char ch = s[0];
    // 先把后续子串的重复字符去掉
    string ans = removeDup(s.substr(1));
    // 再判断当前字符是否在后续去重结果中存在，不存在才拼接
    if (ans.find(ch) == string::npos) {
        return ch + ans;
    }
    return ans;
}

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