如何在不排序的前提下实现字符串去重功能？

你当前的排序实现会打乱字符原本的出现顺序，输出的是字典序的去重结果，和你给出的"allcbcd" -> "alcbd"测试用例预期不符。无需排序的去重方案完全可以实现需求，还能保留字符首次出现的顺序，时间复杂度为O(n)，比排序方案的O(nlogn)效率更高。

核心逻辑是用一个标记容器记录已经出现过的字符，遍历原字符串时仅将首次出现的字符加入结果集即可。

C++实现代码 #

#include <iostream>
#include <string>

using namespace std;

string removeDup(string s) {
    // 标记ASCII字符是否已出现，初始值全为false
    bool seen[128] = {false};
    string res;
    for (char c : s) {
        unsigned char uc = static_cast<unsigned char>(c);
        if (!seen[uc]) {
            res += c;
            seen[uc] = true;
        }
    }
    return res;
}

int main() {
    cout << removeDup("allcbcd") << endl; // 输出alcbd，符合测试用例要求
    return 0;
}

扩展说明 #

• 如果需要处理Unicode等非ASCII字符，将布尔数组替换为unordered_set<char>（或对应宽字符类型的容器）即可，核心逻辑不变。
• 如果你偏好递归实现，只需将标记容器作为递归参数传递即可，不需要引入排序步骤。

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