解題說明
Optimal Partition of String
題目描述：
給定一個字串 s，將其分割為最少數量的子字串，使得每個子字串中的字元都是唯一的（不重複）。回傳最少的子字串數量。
解題思路： 使用貪心策略：盡可能讓每個子字串越長越好。
- 維護一個集合（或位元遮罩）記錄當前子字串中已出現的字元。
- 遍歷字串，若當前字元已在集合中，則開始一個新的子字串（答案 +1），清空集合。
- 將當前字元加入集合。
- 初始答案為 1（至少有一個子字串）。
由於只有 26 個小寫字母，可以用一個 32 位整數的位元遮罩代替集合。
C++ 解法
複雜度分析
時間複雜度：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 partitions其他解法
HashSet 法 O(n)：用 unordered_set<char> 代替位元遮罩。邏輯相同，但空間常數略大且有雜湊開銷。
最後出現位置法 O(n)：記錄每個字元最後出現的位置。若當前字元的最後出現位置在當前子字串的起始位置之後，則需要分割。空間 O(26)。
延伸思考
- 如果允許每個子字串中每個字元最多出現 k 次（而非 1 次），做法如何修改？
- 如何證明貪心策略（每個子字串盡可能長）一定是最優的？
- 如果字元集不限於小寫字母，位元遮罩法還能用嗎？需要如何調整？