P2852. 全量和已占用字符集

解题思路

非常简单又直接的题目。

数据预处理和储存

首先我们需要对输入的字符串进行解析，先根据切割符 "@" 将输入的原始字符串分割成前后两部分，s1 和 s2。将 s1 和 s2 分割为若干仅包含 "字母:数字" 的格式。即：

此处特别注意，s2 有可能为空，如果为空则直接设置 lst2 为空列表即可。

由于这是一个计数问题，很容易想到再进一步将全量字符集和已用字符储存在哈希表计数器中，将 "字母:数字" 格式分割为字母和数字。即：

数据计算

数据计算方面也非常简单，我们仅需要考虑全量字符集 dic1 中的每一个键 k，将其出现的次数 dic1[k] 减去其在已用字符集中的出现次数 dic2[k]，就可以得到剩余字符的情况，储存在 ans_dic 中。即：

要特别注意，如果 dic1[k]-dic2[k] == 0，则无需储存。修改代码为：

输出最终结果

最终再次按照顺序遍历全量字符集，遍历 lst1 中的元素 item。将 "字母:数字" 格式分割为字母 ch 和数字。并且将在 ans_dic 中的次数情况，储存在一个新的列表 ans 中。

由于 ch 的数量可能降为 0，所以需要额外多一步判断 ch 是否位于 ans_dic 中。即：

复杂度分析 设全量字符集有 m 个「字母:数字」项、已用字符集有 k 项，输入串总长为 L。

• 按 "@" 与 "," 切分输入：O(L)。
• 两个 for 循环分别遍历 lst1 与 lst2 构建 dic1、dic2：每项做一次 split 与整数转换，合计 O(L)。
• 构建 ans_dic 的字典推导遍历 dic1 的键：O(m)，其中哈希表查询是均摊 O(1)。
• 最后再按 lst1 的原始顺序遍历一次拼装输出：O(m)。

整体时间复杂度为 O(L)，与输入长度线性相关；全程没有排序和嵌套循环，瓶颈只是几次线性扫描。空间复杂度为 O(m + k)，用于 dic1、dic2、ans_dic 与答案列表。 附注：C++ 参考实现使用 std::map，单次读写带 O(log m) 因子，总体为 O(L log m)，量级上与 Python 版没有实质差别。