給定字串
s，將其分割成最少的子字串，使每個子字串中的字元都不重複。回傳最少的分割數量。
Example:
Input: s = “abacaba” Output: 4 （“ab”, “ac”, “ab”, “a”）
Intuition
TIP
核心思路：Greedy——盡可能讓每個子字串最長（包含最多不重複字元）。遇到重複字元時就開始新的子字串。
- 使用 HashSet 追蹤當前子字串的字元
- 遇到已存在的字元 -> 計數+1，清空 Set，開始新子字串
- Greedy 正確性：讓每段盡量長不會讓後面的分割更差
Approaches
1. HashSet Greedy — O(n) / O(26)
- Idea: 用 HashSet 記錄當前子字串的字元，遇到重複就清空並計數
- Time:
O(n)- 一次遍歷 - Space:
O(26)=O(1)- 最多 26 個字母
class Solution {
fun partitionString(s: String): Int {
val seen = HashSet<Char>()
var count = 1
for (c in s) {
if (c in seen) {
count++
seen.clear()
}
seen.add(c)
}
return count
}
}⭐ 2. Bitmask Greedy — O(n) / O(1)
- Idea: 用 26-bit 整數取代 HashSet，每個 bit 代表一個字母是否出現過
- Time:
O(n)- 一次遍歷 - Space:
O(1)- 一個整數
class Solution {
fun partitionString(s: String): Int {
var mask = 0
var count = 1
for (c in s) {
val bit = 1 shl (c - 'a')
if (mask and bit != 0) {
count++
mask = 0
}
mask = mask or bit
}
return count
}
}WARNING
初始化 count = 1 而非 0，因為即使沒有重複，字串本身就是一個子字串。最後一段子字串不會觸發 count++，所以初始值要從 1 開始。
🔑 Takeaways
- Pattern: 最少分割使每段無重複 -> Greedy 最長延伸
- Key trick: Bitmask 取代 HashSet 在小字母表場景下更高效；Greedy 的正確性來自於「當前段越長，後面的壓力不會更大」