Java高效实现移除字符串中所有重复字符（不使用contains/indexOf）

首先明确需求边界：不使用contains、indexOf方法，删除所有出现次数≥2的字符的全部实例，仅保留仅出现1次的字符，且保持原有字符顺序。

原有实现的问题 #

你之前写的两个实现都有明显缺陷：

1. 正则方案：([a-z]+)\1仅能匹配连续重复的字母片段，无法统计字符在整个字符串中的全局出现次数，根本无法覆盖非连续重复的场景，比如示例里的abcdcb中b、c都是隔了其他字符重复的，完全匹配不到。
2. 循环替换方案：时间复杂度为O(n²)，每遍历一个字符就要执行一次全字符串替换操作，字符串长度上来之后性能会暴跌；另外用String直接拼接结果会生成大量无用的临时字符串对象，额外内存开销很高。

最优实现方案（O(n)时间复杂度） #

核心思路是两次线性遍历，用计数数组统计字符频次，完全不需要用到被禁用的方法，性能拉满：

1. 第一次遍历原字符串，用数组统计每个字符的出现次数（如果只处理小写字母开26长度数组即可，处理全ASCII开256长度，需要支持Unicode可以替换为HashMap<Character, Integer>，数组性能最优）
2. 第二次遍历原字符串，把所有计数为1的字符按顺序拼接到结果中即可，拼接用StringBuilder避免不必要的对象创建。

代码实现：

public static String removeAllDuplicateChars(String s) {
    // 边界情况直接返回
    if (s == null || s.length() < 2) {
        return s == null ? "" : s;
    }
    int[] charCount = new int[256]; // 适配全ASCII字符集
    char[] charArr = s.toCharArray();

    // 第一次遍历统计频次
    for (char c : charArr) {
        charCount[c]++;
    }

    // 第二次遍历拼接仅出现一次的字符
    StringBuilder result = new StringBuilder();
    for (char c : charArr) {
        if (charCount[c] == 1) {
            result.append(c);
        }
    }
    return result.toString();
}

这个实现的优势：

• 全程未调用contains、indexOf方法，完全符合要求
• 时间复杂度严格为O(n)，仅需两次遍历字符串，无论字符串多长性能都很稳定
• 计数数组的访问是O(1)时间，固定内存开销不随字符串长度增长
• 用StringBuilder做结果拼接，避免了String不可变特性带来的额外性能损耗

补充说明：别硬用正则实现这个需求，正则本身不擅长全局跨位置的频次统计，就算硬写出能跑的正则，可读性和性能都会非常差，完全没必要。

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