763. 划分字母区间

📝 题目描述

给你一个字符串 s，将其划分为尽可能多的片段，同一字母最多出现在一个片段中。返回每个片段的长度列表。

注意：划分结果需满足“按顺序拼接片段后，得到的字符串仍是 s”。

---

📌 示例

示例 1

输入：

s = "ababcbacadefegdehijhklij"

输出：

[9,7,8]

解释：划分结果为 "ababcbaca"、"defegde"、"hijhklij"，每个字母仅出现在一个片段中。

示例 2

输入：

s = "eccbbbbdec"

输出：

[10]

解释：所有字母无法拆分到多个片段，只能作为一个整体。

---

🚀 最优解：贪心算法（记录字符最远位置）

🔍 思路解析

核心目标是“尽可能多划分片段”，需保证当前片段包含所有已出现字母的最远位置：

1. 先遍历字符串，记录每个字符的最后出现位置（用数组map存储，下标对应字母，值对应索引）；
2. 再遍历字符串，维护两个变量：
   • start：当前片段的起始索引；
   • end：当前片段的最远结束索引（随字符遍历更新为“当前字符的最后位置”）；
3. 当遍历到end时，说明当前片段已包含所有必要字符，记录片段长度并更新start。

---

✅ 完整代码（Java）

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read the input string
        String s = scanner.nextLine();

        Solution solution = new Solution();
        List<Integer> result = solution.partitionLabels(s);

        // Print the result
        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        // 记录每个字母的最后出现位置（a-z对应下标0-25）
        int[] map = new int[26];
        for (int i = 0; i < n; i++) {
            map[s.charAt(i) - 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int start = 0; // 当前片段起始索引
        int end = 0;   // 当前片段的最远结束索引

        for (int i = 0; i < n; i++) {
            // 更新当前片段的最远结束索引
            end = Math.max(end, map[s.charAt(i) - 'a']);
            // 遍历到当前片段的最远位置，划分片段
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1; // 更新下一个片段的起始索引
            }
        }

        return res;
    }
}

---

🧠 通俗易懂解释

可以把问题理解为“给字母‘画地盘’”：

• 每个字母都有自己的“最远地盘”（最后出现的位置）；
• 遍历字符串时，要确保当前片段“包住”所有已遇到字母的地盘：
  • 比如遍历到a，发现它的地盘到索引8，那当前片段至少要到8；
  • 遍历到b，发现它的地盘到索引5（在8以内，不用扩展）；
  • 遍历到c，发现它的地盘到索引7（仍在8以内）；
  • 当遍历到索引8时，所有已遇到字母的地盘都被包住了，此时划分片段，长度为8-0+1=9。

---

⏱ 时间复杂度

O(n)

• 第一次遍历字符串记录最远位置：O(n)；
• 第二次遍历字符串划分片段：O(n)；
• 总时间复杂度为O(n)，n为字符串长度。

---

💾 空间复杂度

O(1)

仅使用固定大小的数组map（长度26，与输入无关）和列表res（存储结果，不计入额外空间），空间复杂度为常数级。

---

//记录每个字母最后的边界，当然后不断更新这一区间的最大边界