LeetCode 763. 划分字母区间

763. 划分字母区间

解题思路

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段

1. 记录每个字母最后出现的位置: 扫描一遍字符串，记录每个字母最后一次出现的位置
2. 开始划分片段，动态扩展当前片段 (start, end) 的边界 end

• 从左到右扫描字符串
• 对于每个字符，查看它的最后出现位置
• 不断扩展当前片段的结束位置 end
• 当走到当前片段的边界时，就完成了一个片段 i == end

3. start = end + 1，开始寻找下一个片段

参考代码

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        int length = s.length();
        
        for(int i = 0; i < length; i ++) {
            last[s.charAt(i) - 'a'] = i;
        }

        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;
        for(int i = 0; i < length; i ++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            // 如果当前位置i等于当前片段的边界end
            // 说明：1. 已经走到了当前片段能到达的最远位置
            //      2. 当前片段内所有字符的最后出现位置都 <= end
            //      3. 可以安全地划分这个片段了
            if(i == end) {
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        return result;
    }
}