LeetCode hot100-80

https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked

763. 划分字母区间
已解答
中等
相关标签
相关企业
提示
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

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

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

又是gpt老师教我的。其实自己看代码能明白这个思想。
我们需要知道每个字符的最后一个出现位置。
比如这个输入输出
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij”
最开始第一个字母就是a，至少要找到a的最终位置才能划分第一个区间。在找a的过程中又囊括了b，c。还好最后一个a后没有出现过b，c了。所以第一个区间就是 “ababcbaca”。第二个区间就从d开始，找到最后一个d的过程中囊括了e，f。且最后一个d后还出现过e，那么d到最后一个d就不足以划分区间，还得把出现的e，f全划分进去。这个功能是在哪里实现的呢。end = Math.max(end, lastIndex.get(s.charAt(i)));当划过第一个d时end更新为最后一个d。当划过第一个e时end已更新为最后一个e。所以他能一直更新子区间的end。

public class Solution {
    public List<Integer> partitionLabels(String s) {
        // 记录每个字符最后出现的索引
        Map<Character, Integer> lastIndex = new HashMap<>();
        
        // 填充每个字符最后出现的位置
        for (int i = 0; i < s.length(); i++) {
            lastIndex.put(s.charAt(i), i);
        }
        
        List<Integer> result = new ArrayList<>();
        int start = 0;  // 当前片段的起始位置
        int end = 0;    // 当前片段的结束位置
        
        // 遍历字符串，划分片段
        for (int i = 0; i < s.length(); i++) {
            // 更新当前片段的结束位置
            end = Math.max(end, lastIndex.get(s.charAt(i)));
            
            // 如果当前位置 i 达到当前片段的结束位置，说明一个片段结束了
            if (i == end) {
                // 记录当前片段的长度
                result.add(i - start + 1);
                // 更新下一个片段的起始位置
                start = i + 1;
            }
        }
        
        return result;
    }
}