题目描述

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

示例 1:

输入: S = "ababcbacadefegdehijhklij"

输出: [9,7,8]

解释:

划分结果为 "ababcbaca", "defegde", "hijhklij"。

每个字母最多出现在一个片段中。

像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

注意:

S的长度在[1, 500]之间。
S只包含小写字母'a'到'z'。

解题思路

假设我们有一个片段是符合要求的，我们给这个片段设一个标签叫a，那字母a最后出现的位置肯定也在这个片段中（如果不在这个片段中，而在其他的地方出现了，就不符合题目一个字母只在一个片段出现的要求）。

在两个a之间，一般来讲也会有其他字母，同理，在这期间其他字母最后一次出现也要包含在这个片段中，这就会导致这个符合要求的片段扩张一部分。举个例子，原字符串是“abccaddbeffe”，则第一个符合要求的片段是“abccaddb”。

利用上述这个思想，我们可以使用如下方法来解题：

构造一个数组，存放给定字符串s中，每个字符最后出现的索引
设置两个指针start和end分别表示符合要求的片段的开始索引和结束索引
按字符遍历字符串，不断更新end的值，直到i == end说明已经搜寻到一个符合要求的片段了，此时重置start的值

Java 实现

public List<Integer> partitionLabels (String s) {

    int[] last = new int[26];

    for (int i = 0; i < s.length(); i++) {

        last[s.charAt(i) - 'a'] = i;

    }

    int start = 0, end = 0;

    List<Integer> ans = new ArrayList<>();

    for (int i = 0; i < s.length(); i++) {

        end = Math.max(end, last[s.charAt(i) - 'a']);

        if (i == end) {

            ans.add(i - start + 1);

            start = end + 1;

        }

    }

    return ans;

}

心得体会

本题贪心算法和双指针的结合

字母

【LeetCode】763-划分字母区间

题目描述

解题思路

Java 实现

心得体会