划分字母区间:每个字母只出现在一个片段(LC763)
哪些公司问过
答案要点
- 先记录每个字母最后一次出现的下标
- 扫描时把当前片段终点end扩展到已见字符的最远出现位置
- 下标等于end时切分,记录片段长度
- 最早可切处就切,保证片段数最多
- 时间O(n),空间O(字符集大小)
易错点
- 遇到重复字符就切,把同一字母拆到两个片段
- 只用当前字符的最后位置更新end,而不是取最大值
- 忘记切分后更新start
面试官常见追问
- 能转化成区间问题吗?
- 如果要返回子串本身而不是长度呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。