将字符串中的重复字符替换为唯一字符的算法与Java实现需求

这是个挺有意思的字符串去重变种问题，我来帮你梳理清楚核心算法思路，再给你一份可直接运行的Java代码。

核心算法思路 #

要解决这个问题，关键是动态跟踪已出现的字符，并为重复字符找到紧邻的下一个可用唯一字符：

• 用一个HashSet<Character>存储已经处理过的唯一字符，这样可以快速判断某个字符是否已存在（查询时间复杂度O(1)）。
• 从左到右遍历字符串的每个字符：
  1. 如果当前字符未在集合中，直接将其加入集合，保留原字符。
  2. 如果当前字符已存在，从该字符的下一个ASCII值对应的字符开始依次查找，直到找到一个未在集合中的字符，用这个字符替换当前字符，并将新字符加入集合。
• 题目限定字符串长度为10-15位，完全不用担心字母表字符耗尽的问题，所以不需要处理找不到可用字符的边界情况。

Java 可运行实现代码 #

import java.util.HashSet;
import java.util.Set;

public class UniqueStringProcessor {
    public static String processDuplicateChars(String input) {
        if (input == null || input.isEmpty()) {
            return input;
        }
        
        char[] charArray = input.toCharArray();
        Set<Character> seenChars = new HashSet<>();
        
        for (int i = 0; i < charArray.length; i++) {
            char current = charArray[i];
            if (!seenChars.contains(current)) {
                // 当前字符未出现过，直接加入集合
                seenChars.add(current);
            } else {
                // 寻找下一个可用的唯一字符
                char replacement = (char) (current + 1);
                while (seenChars.contains(replacement)) {
                    replacement++;
                }
                // 替换当前字符并更新集合
                charArray[i] = replacement;
                seenChars.add(replacement);
            }
        }
        
        return new String(charArray);
    }

    public static void main(String[] args) {
        String testInput = "creepfe";
        String result = processDuplicateChars(testInput);
        System.out.println("输入: " + testInput);
        System.out.println("输出: " + result); // 输出应为crefpgh
    }
}

测试示例与过程解析 #

以输入"creepfe"为例，处理过程如下：

1. 初始字符数组：['c','r','e','e','p','f','e']，集合seenChars为空。
2. 处理第1个字符'c'：未出现过，加入集合，集合变为{'c'}。
3. 处理第2个字符'r'：未出现过，加入集合，集合变为{'c','r'}。
4. 处理第3个字符'e'：未出现过，加入集合，集合变为{'c','r','e'}。
5. 处理第4个字符'e'：已存在，从'e'+1='f'开始查找，'f'未在集合中，替换为'f'，集合加入'f'，数组变为['c','r','e','f','p','f','e']。
6. 处理第5个字符'p'：未出现过，加入集合，集合变为{'c','r','e','f','p'}。
7. 处理第6个字符'f'：已存在，从'f'+1='g'开始查找，'g'未在集合中，替换为'g'，集合加入'g'，数组变为['c','r','e','f','p','g','e']。
8. 处理第7个字符'e'：已存在，依次查找'f'（存在）、'g'（存在）、'h'（不存在），替换为'h'，集合加入'h'，最终数组为['c','r','e','f','p','g','h']，即输出"crefpgh"。

补充说明 #

• 大小写字符区分：由于HashSet<Character>是基于字符的ASCII值存储的，'A'和'a'的ASCII值不同，所以会被视为不同的字符，完全符合题目要求。
• 时间复杂度：每个字符最多遍历一次，查找替换字符的过程在题目限定长度下可以忽略不计，整体时间复杂度为O(n)（n为字符串长度）。

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