一、题目大意

标签: 贪心

https://leetcode.cn/problems/partition-labels

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

示例：

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

提示：

• S 的长度在[1, 500]之间。

• S 只包含小写字母 'a' 到 'z' 。

二、解题思路

一个字符串 S，将其尽可能多的分割为子字符串，条件是每种字符最多只能出现在一个子串中。上面的示例中，字符串 S 中有多个 a，这些 a 必须只能在第一个子串中，字母 e 出现在第二个子串中。这道题难点就是如何找到字符串的断点，即拆分成为子串的位置。观察上述例子，一旦某个字母多次出现，那么其最后一个出现位置必须要在当前子串中，字母 a，e，j 分别是三个子串中的结束字母。所以我们关注的是每个字母最后的出现位置，我们可以使用一个 Map 来建立字母和其最后出现位置之间的映射，建立好映射之后，就需要开始遍历字符串 S，我们维护一个 start 变量，是当前子串的起始位置，还有一个 last 变量，是当前子串的结束位置，每当我们遍历到一个字母，需要在 Map 中提取出其最后一个位置，因为一旦当前子串饮食了一个字母，其必须饮食所有的相同字母，所以我们要不停的用当前字母的最后一个位置来更新 last 变量，只有当 i 和 last 相同了，即 i=last 时，当前子串饮食了所有已出现过的字母的最后一个位置，即之后的字符串不会有之前出现过的字母了，此时就应该是断开的位置，我们将子串长度加入到结果中。

三、解题方法

3.1 Java 实现

public class Solution {    public List<Integer> partitionLabels(String s) {        Map<Character, Integer> map = new HashMap<>();        char[] cArr = s.toCharArray();        for (int i = 0; i < cArr.length; i++) {            map.put(cArr[i], i);        }
        List<Integer> res = new ArrayList<>();        int start = 0;        int last = 0;        for (int i = 0; i < cArr.length; i++) {            last = Math.max(map.get(cArr[i]), last);            if (i == last) {                res.add(last - start + 1);                start = last + 1;            }        }
        return res;    }}

四、总结小记

• 2022/7/28 把思路理清了，代码就顺理成章出来了