給定一個字串
s，將它分割成盡可能多的片段，使得每個字母最多只出現在一個片段中。回傳每個片段的長度列表。
Example:
Input: s = “ababcbacadefegdehijhklij” Output: [9,7,8]
Intuition
TIP
記錄每個字元的最後出現位置，遍歷時維護當前片段的邊界，邊界到達時切割。
- 先掃描一遍記錄每個字元的最後出現位置
lastIndex - 再次遍歷，維護當前片段的右邊界
end = max(end, lastIndex[c]) - 當
i == end時，表示當前片段內的所有字元都不會再出現了，可以切割
Approaches
1. Brute Force (merge intervals) — O(n + k log k) / O(k)
- Idea: 為每個字元建立 [首次出現, 最後出現] 的區間，然後做區間合併。
- Time:
O(n + k log k)，k 為不同字元數 - Space:
O(k)
class Solution {
fun partitionLabels(s: String): List<Int> {
val first = IntArray(26) { -1 }
val last = IntArray(26) { -1 }
for (i in s.indices) {
val c = s[i] - 'a'
if (first[c] == -1) first[c] = i
last[c] = i
}
val intervals = mutableListOf<IntArray>()
for (i in 0 until 26) {
if (first[i] != -1) intervals.add(intArrayOf(first[i], last[i]))
}
intervals.sortBy { it[0] }
val result = mutableListOf<Int>()
var start = intervals[0][0]
var end = intervals[0][1]
for (i in 1 until intervals.size) {
if (intervals[i][0] <= end) {
end = maxOf(end, intervals[i][1])
} else {
result.add(end - start + 1)
start = intervals[i][0]
end = intervals[i][1]
}
}
result.add(end - start + 1)
return result
}
}⭐ 2. Greedy (Single Pass) — O(n) / O(1)
- Idea: 預處理每個字元的最後位置後，一次遍歷即可完成切割。
- Time:
O(n) - Space:
O(1)（26 個字元的陣列為常數）
class Solution {
fun partitionLabels(s: String): List<Int> {
val lastIndex = IntArray(26)
for (i in s.indices) {
lastIndex[s[i] - 'a'] = i
}
val result = mutableListOf<Int>()
var start = 0
var end = 0
for (i in s.indices) {
end = maxOf(end, lastIndex[s[i] - 'a'])
if (i == end) {
result.add(end - start + 1)
start = i + 1
}
}
return result
}
}🔑 Takeaways
- Pattern: 區間邊界擴展 — 動態更新右邊界，到達邊界時做決策
- Key trick: 「每個字元的最後出現位置」決定了片段的最小範圍；這個模式也適用於其他「不重疊分割」問題