Snapchat VO 面试真题解析：最长子串中的至多 K 个不同字符

Find the longest substring of a given string with at most K unique characters.

Example:

("cabbacc", 1) -> "bb" or "cc"
("cabbacc", 2) -> "abba"
("cabbacc", 3) -> "cabbacc"

这道题考察的是“至多 K 个不同字符的最长子串”，经典解法是滑动窗口配合哈希表统计窗口内每个字符的出现次数。我们从左到右扩展右指针，当不同字符数超过 K 时，再移动左指针并同步减少计数，直到窗口重新满足条件。过程中持续更新最长合法区间即可。示例中，字符串 "cabbacc" 在 K=1 时最长答案可以是 "bb" 或 "cc"，K=2 时可得到 "abba"，K=3 时整个字符串都满足条件。