1. 題目

給定一個字符串 s，我們需要將其劃分為盡可能多的部分，使得同一字母最多出現在一個部分中。

例如：字符串 "ababcc" 可以劃分為 ["abab", "cc"]，但要避免 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 這樣的劃分方式（因為它們包含了同一個字母出現在多個部分的情況）。

注意：劃分后的部分順序必須與原字符串順序一致，所有部分拼接起來仍然等于 s。
返回：這些部分的長度組成的列表。

2.?分析

這道題目是一個典型的貪心算法問題，解法類似于區間合并問題。

關鍵思路

1. 記錄每個字母的最遠出現位置
   • 用?last_occurrence?字典保存每個字符在字符串?s?中最后出現的位置（即最右邊的索引），這樣可以確定該字符所屬的最小子串范圍。
2. 滑動窗口遍歷，確定當前部分的結束點
   • 用?start?和?end?表示當前部分的起始和結束位置。
   • 遍歷字符串時，不斷更新?end，使其變為已遍歷字符的最遠出現位置。
   • 當?i == end?時，說明當前部分可以切分，記錄長度，并更新?start?到?end + 1。

3. 完整代碼

def partition_labels(s):last_occurrence = {char: idx for idx, char in enumerate(s)}  # 記錄每個字母的最后出現位置start = end = 0result = []for i, char in enumerate(s):end = max(end, last_occurrence[char])  # 更新當前部分的結束點if i == end:  # 找到一個符合條件的部分result.append(end - start + 1)start = end + 1  # 更新下一部分的起始點return result
print(partition_labels("ababcc"))

示例分析：s = "ababcc"

1. last_occurrence = {'a': 2, 'b': 3, 'c': 5}
2. 遍歷過程：
   • i = 0,?char = 'a',?end = max(0, 2) = 2
   • i = 1,?char = 'b',?end = max(2, 3) = 3
   • i = 2,?char = 'a'（滿足?i == end = 2），記錄長度?2 - 0 + 1 = 3（"aba"）?？
   • （這里需要更正！i = 2?時的?end = 3，不等于?i，不會觸發?append。）
   • i = 3,?char = 'b'（滿足?i == end = 3），記錄長度?3 - 0 + 1 = 4（"abab"）
   • i = 4,?char = 'c',?end = max(3, 5) = 5
   • i = 5,?char = 'c'（滿足?i == end = 5），記錄長度?5 - 4 + 1 = 2（"cc"）
3. 最終結果:?[4, 2]（["abab", "cc"]）?

在 partition_labels 算法中，end 表示當前部分的最遠結束位置。為了保證同一字符僅出現在一個部分里，我們需要確保其所有出現的范圍都能被當前部分完全覆蓋。max(end, last_occurrence[char]) 的作用是不斷擴展當前部分的右邊界，以確保：當前字符的所有出現都被覆蓋，后續字符不會跨越當前部分。

以 s = "ababcc" 為例：

字符?char	last_occurrence[char]	end（更新前）	new_end = max(end, last)	操作
'a'?(i=0)	2	0	max(0, 2) = 2	end=2
'b'?(i=1)	3	2	max(2, 3) = 3	end=3
'a'?(i=2)	2	3	max(3, 2) = 3	end=3
'b'?(i=3)	3	3	max(3, 3) = 3	觸發分割
'c'?(i=4)	5	3	max(3, 5) = 5	end=5
'c'?(i=5)	5	5	max(5, 5) = 5	觸發分割

當 i == end 時，觸發分隔的原因：

說明：當前部分的所有字符已經處理完畢，

• 已經遍歷到?i = end，且在這個位置之前的所有字符的最遠出現位置?last_occurrence[char]?都 ≤?end（因為?end?是由?max(last_occurrence[char])?決定的）。
• 換句話說，這個部分已經囊括了所有必須包含的字符（同一字母的所有出現都被包含在當前部分）。