📃 题目描述

题目链接：763. 划分字母区间 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

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

🔔 解题思路

以 ababcbacadefegdehijhklij 举例

1. 第 1 个字符 a 加入第一个片段，这是确定的，然后找到 a 出现的最后一个位置，这之间的所有字符都加入第一个片段，若最后一个 a 的后面还存在第一个片段内的字符，则一并加入。所以，第一个区间就是 ababcbaca
2. 同样的，紧接着第一个区间之后，将 d 加入第二个区间，然后找到 d 出现的最后一个位置，这之间的所有字符都加入第二个片段，若最后一个 d 的后面还存在第二个片段内的字符，则一并加入。所以，第二个区间就是 defegde
3. .....

具体该怎么用代码表示呢？

一句话：如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了

可以分为如下两步：

• 统计每一个字符最后出现的位置
• ⭐ 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前遍历到的下标 i 相等了，则说明找到了分割点

class Solution {
    public List<Integer> partitionLabels(String s) {
        // 记录每个字符的最远边界, 总共只有 26 个字符，可以使用数组代替哈希表
        int edge[] = new int[26];
        for (int i = 0; i < s.length(); i ++) {
            edge[s.charAt(i) - 'a'] = i;
        }

        // 记录每个片段的长度
        List<Integer> res = new ArrayList<>();
        // 记录字符的最远边界
        int max_edge = 0;
        // 记录每个片段的起始下标
        int start = 0;
        for (int i = 0; i < s.length(); i ++) {
            // 更新最远边界
            max_edge = Math.max(max_edge, edge[s.charAt(i) - 'a']);
            if (i == max_edge) {
                res.add(i - start + 1);
                // 下一个片段的起始位置
                start = i + 1;
            }
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)