題目描述:
給定一個字串 s,將其分割為最少數量的子字串,使得每個子字串中的字元都是唯一的(不重複)。回傳最少的子字串數量。
解題思路: 使用貪心策略:盡可能讓每個子字串越長越好。
由於只有 26 個小寫字母,可以用一個 32 位整數的位元遮罩代替集合。
時間複雜度:O(n) — 單次遍歷字串。
空間複雜度:O(1) — 位元遮罩只需一個整數(26 位)。
1. Set partitions = 1, seen = 0 (bitmask)
2. For each character c in s:
a. bit = 1 << (c - 'a')
b. If seen & bit != 0:
- Increment partitions
- Reset seen = 0
c. seen |= bit
3. Return partitionsHashSet 法 O(n):用 unordered_set<char> 代替位元遮罩。邏輯相同,但空間常數略大且有雜湊開銷。
最後出現位置法 O(n):記錄每個字元最後出現的位置。若當前字元的最後出現位置在當前子字串的起始位置之後,則需要分割。空間 O(26)。