更新時間：2025-03-30

• 算法題解目錄匯總：算法刷題記錄——題解目錄匯總
• 技術博客總目錄：計算機技術系列博客——目錄頁

優先整理熱門100及面試150，不定期持續更新，歡迎關注！

---

763. 劃分字母區間

給你一個字符串 s 。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。例如，字符串 "ababcc" 能夠被分為 ["abab", "cc"]，但類似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的劃分是非法的。

注意，劃分結果需要滿足：將所有劃分結果按順序連接，得到的字符串仍然是 s 。

返回一個表示每個字符串片段的長度的列表。

示例 1：

輸入：s = "ababcbacadefegdehijhklij"
輸出：[9,7,8]

劃分結果為 “ababcbaca”、“defegde”、“hijhklij” 。每個字母最多出現在一個片段中。
像 “ababcbacadefegde”, “hijhklij” 這樣的劃分是錯誤的，因為劃分的片段數較少。

示例 2：

輸入：s = "eccbbbbdec"
輸出：[10]

提示：

• 1 <= s.length <= 500
• s 僅由小寫英文字母組成

---

方法一：貪心算法

1. 記錄每個字符的最后出現位置：首先遍歷字符串，記錄每個字符最后一次出現的索引，為后續分割提供依據。
2. 維護當前片段的起止位置：再次遍歷字符串，動態維護當前片段的結束位置，確保所有已遍歷字符的最后出現位置均包含在當前片段中。當遍歷到當前片段的結束位置時，立即分割，確保每個字符僅屬于一個片段，并開始下一個片段的處理。

代碼實現(Java)：

class Solution {public List<Integer> partitionLabels(String s) {// 記錄每個字符的最后出現位置int[] lastOccurrence = new int[26];int length = s.length();for (int i = 0; i < length; i++) {char c = s.charAt(i);lastOccurrence[c - 'a'] = i;}List<Integer> partitions = new ArrayList<>();int start = 0, end = 0;for (int i = 0; i < length; i++) {char currentChar = s.charAt(i);// 擴展當前片段的結束位置end = Math.max(end, lastOccurrence[currentChar - 'a']);// 當遍歷到當前片段的結束位置時，分割并記錄if (i == end) {partitions.add(end - start + 1);start = end + 1; // 下一個片段的起始位置}}return partitions;}
}

動態規劃法復雜度分析：

• 時間復雜度：O(n)，其中 n 是字符串的長度。兩次遍歷字符串的時間復雜度均為 O(n)。
• 空間復雜度：O(1)，使用固定大小的數組存儲字符的最后出現位置。

---

方法二：合并區間（理論補充）

1. 生成字符區間：記錄每個字符的首次和最后一次出現的位置，生成區間集合。
2. 合并重疊區間：將所有重疊的區間合并，合并后的每個區間對應一個最終的分段。

合并區間法復雜度分析：

• 時間復雜度：O(n + m log m)，其中 m 是不同字符的數量（最多26個），實際性能不如貪心算法。
• 空間復雜度：O(m)，需要存儲所有字符的區間。

---

聲明

1. 本文版權歸 CSDN 用戶 Allen Wurlitzer 所有，遵循CC-BY-SA協議發布，轉載請注明出處。
2. 本文題目來源 力扣-LeetCode ，著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。