代码空间复杂度分析：去除无空格字符串重复字符

问题说明 #

给定一个无空格字符串，需去除其中重复字符且保持字符原始顺序不变。

示例 #

• 输入：S = "zvvo"
• 输出："zvo"
• 解释：仅保留字符的首次出现。

以下是实现该功能的Java代码，现分析其空间复杂度：

public class Solution {
    public String removeDups(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i< s.length(); i++){
            String ch = Character.toString(s.charAt(i));
            if (sb.indexOf(ch) == -1)
                sb.append(ch);
        }
        return sb.toString();
    }
}

空间复杂度分析 #

• 最坏场景：当输入字符串中所有字符均不重复时，StringBuilder会存储全部字符，此时空间复杂度为 O(n)（n为输入字符串长度）。
• 一般场景：若输入存在重复字符，空间复杂度由字符串中唯一字符的数量k决定，即 O(k)，k ≤ n。
• 临时变量开销：代码中仅用了单个字符的临时变量ch，这部分空间为常数级O(1)，对整体复杂度无影响。
• 特殊情况补充：如果输入字符集是固定大小的（比如ASCII字符集，最多128个唯一字符），那么k的最大值是固定值，此时空间复杂度可视为O(1)。但通用场景下我们默认按字符集无限制的情况分析。

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