题目重点：Uber New Grad Phone Screen 面经中的 S/M/L 字符串排序题。比较通用比较排序与固定值域计数，区分面试官约束和候选人主动扩展。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入字符串每个字符代表一个尺码，只允许 S、M、L，目标按 S<M<L 排序并返回同长度字符串。
- 示例代码遇到未知字符报错；题目描述主动扩展时选择忽略未知值，但这不是面试官给的正式规则，不能默认丢弃输入。
- 空字符串返回空字符串，重复尺码保留原数量。
解题路线
- 通用解可定义 rank(S)=0、rank(M)=1、rank(L)=2，用比较排序，O(n log n)。先确认输入约束，再优化。
- 由于合法值域固定且只有三种，单次扫描累计各尺码个数，最后按 S、M、L 的数量拼接输出，O(n)。
- 检查结果长度与各类计数和输入一致；如果扩展到 XS/XL 等，传入有序尺码表并对每类计数，复杂度 O(n+m)，m 是合法尺码数。
手动走一遍
输入 "LMSMS"，统计 S=2、M=2、L=1，返回 "SSMML"。输入 "SXL" 含未知 X，训练代码报错；若现场要求忽略 X，需明确改为 "SL"，不能未经确认丢值。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Sort a string whose only legal sizes are S, M, L."""
def sort_sizes(sizes: str) -> str:
counts = {"S": 0, "M": 0, "L": 0}
for size in sizes:
if size not in counts:
raise ValueError(f"unknown size: {size}")
counts[size] += 1
return "S" * counts["S"] + "M" * counts["M"] + "L" * counts["L"]
复杂度
扫描输入 O(n)，构造长度 n 的输出 O(n)，计数表 O(1) 额外空间（不含结果）；通用比较排序 O(n log n) 时间。
易错点与追问
容易失分的边界
- 按字符字典序排序可能得到 L、M、S，而业务顺序是 S、M、L；必须显式 rank。
- 把未知值静默忽略是题目描述自行探索的扩展，会改变输出长度；正式题目只确认 S/M/L。
- 如果输入实际上是 token 列表而不是单字符字符串，逐字符遍历会拆错 XS/XL；题目明确澄清为 string 且仅 S/M/L。
继续深挖
- 若排序对象是包含尺码和原始记录 ID 的对象，计数桶按尺码保留原相对顺序可得到稳定排序。
- 若尺码集合动态配置，可用 rank 表校验合法值并选择比较排序；值域很小且顺序固定时再转计数桶。
