优化字符串数值转换代码：解决大输入超时问题

首先明确题目核心要求：

给定一个输入字符串，字符串中的每个符号如果是首次出现，则将其替换为‘1’；否则替换为该符号已出现的次数。字符可能包含非ASCII字符，出现次数不会超过20亿。

你已经通过修改实现找到了正确的优化方向，不过我们先来拆解原代码的核心瓶颈，再看看怎么进一步打磨代码，让它更高效地处理超大输入：

原实现的性能瓶颈分析 #

你的前两种实现都踩了几个影响超大输入处理的关键坑：

• 两次完整遍历+预统计开销：先用流式API统计所有字符的出现次数，这已经是一次完整的O(n)遍历；然后又反向遍历字符串修改计数，相当于第二次O(n)遍历。而且split("")会把字符串拆成大量单个字符的小字符串，内存占用和GC压力都很大。
• 冗余的中间操作：第一种实现里的StringBuilder拼接→拆分→反转→合并，第二种里的String[]数组存储，这些额外的操作都会增加内存开销和处理时间，对于超长字符串来说，这些开销会被成倍放大。
• 频繁创建字符串对象：每次String.valueOf(s.charAt(i))都会生成一个新的String对象，几十万甚至几百万次的对象创建会严重拖慢程序运行速度。

你改进后的代码的优势 #

你基于建议写的第三种实现已经抓住了核心优化点：

• 单次遍历完成所有操作：一边遍历字符串，一边维护计数，同时直接构建结果，从两次遍历降到了单次遍历，时间复杂度的常数项大幅降低。
• 用StringBuilder直接构建结果：避免了中间数组和字符串拼接的冗余操作，append操作的均摊时间复杂度是O(1)，效率很高。

不过这里还有可以进一步优化的空间，让代码在处理超大输入时更丝滑：

进一步优化的最终版本 #

我们可以把Map的键从String改成Character，彻底避免单个字符转字符串的对象创建开销；同时预先设置StringBuilder的容量，避免内部数组扩容：

import java.util.HashMap;
import java.util.Map;

public class JomoPipi {
    public static String numericals(String s) {
        Map<Character, Integer> occurrences = new HashMap<>();
        // 预先设置StringBuilder容量，和输入字符串长度一致，避免扩容
        StringBuilder result = new StringBuilder(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 获取当前计数，不存在则默认0，然后加1
            int count = occurrences.getOrDefault(c, 0) + 1;
            occurrences.put(c, count);
            result.append(count);
        }
        return result.toString();
    }
}

这个版本的关键优化点： #

• 用char作为Map键：直接操作原始字符类型，省去了每次创建String对象的开销，减少了GC的频率，对于超长字符串来说，这个优化的效果非常明显。
• 预先初始化StringBuilder容量：因为我们知道结果字符串的长度和输入字符串完全相同，预先设置容量可以避免StringBuilder内部数组的多次扩容（每次扩容都会复制数组），提升整体效率。
• 简化计数逻辑：用getOrDefault一行完成计数的获取和递增，代码更简洁，同时避免了多次调用putIfAbsent和get的冗余操作。

为什么这个版本适合超大输入？ #

• 严格的O(n)时间复杂度：只需要遍历输入字符串一次，每个字符的处理都是平均O(1)的哈希表操作，没有额外的遍历或冗余计算。
• 可控的内存开销：哈希表的大小只取决于字符串中不同字符的数量，即使是GB级的字符串，只要不同字符数不多，内存占用就很小；StringBuilder的内存占用和输入字符串长度成正比，没有额外的冗余。
• 最小化对象创建：几乎没有临时对象产生，垃圾回收的压力降到最低，在处理超大输入时不会因为GC停顿导致超时。

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