LeetCode 3803: Count Residue Prefixes

基本資料

#

難易度: easy 第一次嘗試：2026-01-11

• 提交紀錄：Accepted（一次通過）

解題思路

#

前綴一個字一個字變長，不同字元數用集合邊掃邊維護（String 模板四）。長度是 i + 1，比較 len(seen) == (i + 1) % 3。

我的解法

#

class Solution:
    def residuePrefixes(self, s: str) -> int:
        seen, res = set(), 0
        for i, ch in enumerate(s):
            seen.add(ch)
            res += len(seen) == (i + 1) % 3
        return res

複雜度

#

時間 O(n)，空間 O(1)（最多 26 種字元）。

要特別避免的錯誤

#

• 長度是 i + 1，不是 i。

面試口說整理

#

我由左到右掃，用集合記前綴裡出現過的字元，每一步比較集合大小和前綴長度 mod 3。時間 O(n)。因為長度 mod 3 最多是 2，不同字元數超過 2 之後就不可能再成立，可以提早結束。