763. 劃分字母區間

本題目，“同一字母最多出現在一個片段中”，因為這句話，所以本質上

這道題目屬于合并區間

---

一、算法邏輯（逐步思路）

? 目標：

將字符串 s 劃分成盡可能多的片段，要求：

• 每個字母最多只出現在一個片段中；
• 所有片段拼接后仍是原始字符串；
• 返回每個片段的長度。

? 實現邏輯：

1. 先預處理：

• • 用字典 last 記錄字符串中每個字母最后一次出現的位置；
  • 例如：s = "ababcbacadefegdehijhklij"，其中 'a' 最后出現在 8，'e' 出現在 15，等等。

1. 開始遍歷劃分：

• • 初始化兩個指針：start 表示當前片段的起點，end 表示當前片段的最遠右端；
  • 遍歷字符串：

• • • 對每個字符 c，更新當前片段的 end 為 max(end, last[c])；
    • 如果當前位置 i == end，說明這個片段封閉了（它包含了所有出現在其中字符的最后位置）：

• • • • 計算這個片段的長度為 end - start + 1；
      • 把它加入答案；
      • 然后更新 start = i + 1，準備開始下一個片段。

---

二、算法核心點

? 核心思想：貪心策略 + 動態區間合并

• 核心貪心策略是：

• • 對于當前片段內出現的所有字母，都要等它們“最后一次出現”后，才可以結束這個片段；
  • 所以，我們用 end 表示當前片段中所有字符的最遠結束點；
  • 一旦遍歷指針 i 到達 end，說明這個片段所有相關字符都封閉了，可以切一刀。

• 這個過程貪心的地方在于：

• • 每次劃分盡可能早地結束當前片段（在剛好滿足“所有字符都只出現在一個片段”的條件下），從而得到更多的片段。

class Solution:def partitionLabels(self, s: str) -> List[int]:last = {c: i for i, c in enumerate(s)}  # 每個字母最后出現的下標ans = []start = end = 0for i, c in enumerate(s):end = max(end, last[c])  # 更新當前區間右端點的最大值if end == i:  # 當前區間合并完畢ans.append(end - start + 1)  # 區間長度加入答案start = i + 1  # 下一個區間的左端點return ans

---

三、復雜度分析

• 時間復雜度：O(n)

• • 第一次遍歷構造 last：O(n)；
  • 第二次遍歷劃分字符串：O(n)；
  • 總共是線性時間復雜度。

• 空間復雜度：O(1)（常數級）

• • 雖然用了一個字典 last，但它最多存 26 個小寫字母，屬于常數空間。

---

? 總結表：

維度	內容
? 思路邏輯	利用每個字符最后出現位置，動態維護區間右邊界，貪心切片
? 核心技巧	貪心：延遲切片直到當前片段中所有字母的最后出現位置都包含為止
? 時間復雜度	O(n)，兩次遍歷字符串
? 空間復雜度	O(1)，字母表大小固定，最多用 26 個鍵值對