763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

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

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

类似跳跃游戏

贪心

类似跳跃游戏。

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 创建一个大小为 26 的数组 last，用于存储字符串 s 中每个字符最后一次出现的索引位置。
        int[] last = new int[26];
        int length = s.length();
        // 遍历字符串 s，更新每个字符（转换为从 0 到 25 的索引）最后一次出现的位置。
        for (int i = 0; i < length; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        
        // 创建一个 ArrayList 来存放每个分区的长度。
        List<Integer> partition = new ArrayList<Integer>();
        // 初始化 start 和 end 变量，其中 start 是当前分区的起始索引，end 是根据当前遍历的字符计算出的当前分区的可能的最远结束索引。
        int start = 0, end = 0;
        // 再次遍历字符串 s。对于每个字符，更新 end 为当前字符最后一次出现位置与当前 end 的较大值。这确保 end 总是当前分区内所有字符的最后出现位置的最大值。
        for (int i = 0; i < length; i++) {
            // 每次都要延续一下end。重点
            end = Math.max(end, last[s.charAt(i) - 'a']);
            // 如果当前索引 i 等于 end，说明到达了当前分区的末尾，可以进行切割。重点。
            // 将当前分区的长度（end - start + 1）添加到结果列表中，然后将 start 更新为 end + 1 开始新的分区。
            if (i == end) {
                partition.add(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
}

• 时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串两次，第一次遍历时记录每个字母最后一次出现的下标位置，第二次遍历时进行字符串的划分。
• 空间复杂度：O(|Σ|)，其中 Σ 是字符串中的字符集。这道题中，字符串只包含小写字母，因此 |Σ|=26。