百度Java面试高频题：字符串去重的多解法探索

在Java技术面试中，字符串处理是高频考点之一，而“如何高效去除字符串中的重复字符”更是被某头部互联网公司（如百度）反复考察的经典问题。该问题不仅考察候选人对基础数据结构的掌握，还能体现其对算法效率、代码简洁性和边界条件的处理能力。本文将从基础实现到进阶优化，系统梳理五种典型解法，并分析其适用场景与性能差异。

一、问题定义与核心挑战

题目描述：给定一个字符串，要求返回一个新字符串，其中所有重复字符均被移除，且保留原始字符的首次出现顺序。例如，输入”banana”应返回”ban”。

关键挑战：

1. 时间复杂度：需避免O(n²)的嵌套循环，尤其是处理长字符串时。
2. 空间复杂度：需权衡是否使用额外数据结构存储已访问字符。
3. 边界条件：需处理空字符串、全重复字符、Unicode字符等特殊情况。

二、解法一：暴力遍历法（基础版）

思路：双重循环遍历字符串，外层循环固定当前字符，内层循环检查后续字符是否重复。

public String removeDuplicates(String s) {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        boolean isDuplicate = false;
        for (int j = 0; j < result.length(); j++) {
            if (s.charAt(i) == result.charAt(j)) {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) {
            result.append(s.charAt(i));
        }
    }
    return result.toString();
}

分析：

• 时间复杂度：O(n²)，嵌套循环导致效率低下。
• 空间复杂度：O(n)，需存储结果字符串。
• 适用场景：仅适用于教学演示或极短字符串。

三、解法二：哈希表优化法（进阶版）

思路：利用HashSet记录已访问字符，单次遍历即可完成去重。

public String removeDuplicates(String s) {
    Set<Character> seen = new HashSet<>();
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!seen.contains(c)) {
            seen.add(c);
            result.append(c);
        }
    }
    return result.toString();
}

分析：

• 时间复杂度：O(n)，HashSet的contains和add操作平均为O(1)。
• 空间复杂度：O(n)，最坏情况下需存储所有字符。
• 优化点：可替换为LinkedHashSet以保持插入顺序（但本题无需额外排序）。

四、解法三：Java 8 Stream API（函数式风格）

思路：利用Stream的distinct()方法结合Collectors.joining()。

public String removeDuplicates(String s) {
    return s.chars()
            .distinct()
            .collect(StringBuilder::new, 
                     StringBuilder::appendCodePoint, 
                     StringBuilder::append)
            .toString();
}

分析：

• 简洁性：代码行数最少，但可读性对新手不友好。
• 性能：底层仍依赖Set实现，与解法二效率相当。
• 适用场景：适合追求代码简洁性的项目，或作为面试中的“语法糖”展示。

五、解法四：位运算优化（仅限ASCII字符）

思路：若字符串仅包含ASCII字符（0-127），可用整型变量的二进制位标记字符是否出现过。

public String removeDuplicates(String s) {
    int seen = 0;
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        int mask = 1 << (c - 'a'); // 假设仅小写字母
        if ((seen & mask) == 0) {
            seen |= mask;
            result.append(c);
        }
    }
    return result.toString();
}

分析：

• 时间复杂度：O(n)，单次遍历。
• 空间复杂度：O(1)，仅使用一个整型变量。
• 局限性：仅适用于字符范围有限的场景（如小写字母、数字等）。

六、解法五：双指针法（原地修改数组）

思路：若允许修改输入字符数组，可用双指针实现O(1)空间复杂度（需转换为字符数组处理）。

public String removeDuplicates(String s) {
    char[] chars = s.toCharArray();
    int tail = 0;
    Set<Character> seen = new HashSet<>();
    for (int i = 0; i < chars.length; i++) {
        if (!seen.contains(chars[i])) {
            seen.add(chars[i]);
            chars[tail++] = chars[i];
        }
    }
    return new String(chars, 0, tail);
}

分析：

• 空间复杂度：O(n)（因HashSet存在），若严格限制空间可改用位运算（如解法四）。
• 适用场景：需结合具体需求权衡空间与时间。

七、性能对比与最佳实践

解法	时间复杂度	空间复杂度	适用场景
暴力遍历法	O(n²)	O(n)	教学演示
哈希表优化法	O(n)	O(n)	通用场景，推荐使用
Stream API	O(n)	O(n)	代码简洁性优先
位运算优化	O(n)	O(1)	字符范围有限（如ASCII）
双指针法	O(n)	O(n)	需原地修改数组时

最佳实践建议：

1. 默认选择：哈希表优化法（解法二），兼顾效率与可读性。
2. 字符范围受限：优先使用位运算（解法四），如处理仅含数字的字符串。
3. 代码简洁性：在团队代码规范允许下，可尝试Stream API（解法三）。
4. 避免暴力解法：除非明确要求展示基础实现，否则应优化至O(n)复杂度。

八、面试官考察点延伸

1. 算法思维：能否从暴力解法逐步优化到最优解。
2. 边界处理：是否考虑空字符串、Unicode字符、大小写敏感等问题。
3. 代码质量：变量命名是否清晰，异常处理是否完善。
4. 扩展能力：若问题扩展为“保留最后一次出现的字符”，如何修改解法？

通过系统掌握多种解法，开发者不仅能应对面试中的变体问题，还能在实际项目中根据需求选择最优实现。