题解 | #分品种#

知识点：贪心

题目要求每组之间的字母不能相同，也就是要将相同的字母放在同一组中，所以我们要找到每一个字母所能达到的最远距离，从第一个字母开始，我们需要遍历至第一个字母出现的最远的位置，同时，若遍历过程中出现其他字母，则也需要将其相同的字母包含其中，也就是要选择出现的字母中所能达到的最远距离。当达到最远距离时，将其归为一组，重复以上步骤，直至将所有字符分组。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型一维数组
     */
    public int[] partitionLabels (String s) {
        // write code here
        List<Integer> list = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        int n = s.length();
        for(int i = 0; i < n; i++) {
            map.put(s.charAt(i), i);
        }
        for(int i = 0; i < n; i++) {
            int start = i;
            int end = map.get(s.charAt(i));
            while(i < end) {
                end = Math.max(end, map.get(s.charAt(i++)));
            }
            list.add(end - start + 1);
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}