遍历字符串更新字典存储字符下标，空间复杂度是O(n)还是O(1)

这个问题的答案取决于你对输入字符集的前提假设，两种结论分别对应不同的约束条件： #

你认为是*O(1)*的逻辑是成立的 #

如果题目明确限定输入字符串仅由小写英文字母组成：

• 字典的键的可能取值最多只有26种，不会随输入字符串长度n的增长而增加
• 遍历过程中覆盖已有键的旧值，不会新增存储空间占用，整个字典的空间大小始终是固定常量
  这种场景下空间复杂度确实是O(1)。

题解给出*O(n)*的原因 #

大部分算法题如果没有明确限定字符集范围，会默认采用通用假设：输入字符串的字符可以是任意可哈希的取值（比如全量ASCII、Unicode字符，甚至自定义类型）：

• 最坏情况输入字符串的所有字符都不重复，字典需要存储n个键值对，空间占用和输入长度n成线性关系
• 这种通用场景下的空间复杂度判定就是O(n)，也是大部分题解默认采用的结论。

补充说明：覆盖旧值的操作只会修改已存储的键对应的值，不会增加额外的空间开销，不会影响空间复杂度的计算。

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