题解 | #分品种#

知识点：贪心 字符串转化

思路：理想状态下，每个字母一组，但是需要规避每组中出现相同字母

子问题最优解 当其遇到最后相同字母，便停下来，这是一组

全局推导：这个推导过程很好实现，可以把子问题看成全局中的一段，第一个解决后，剩下的字符串s继续重复操作即可

时间复杂度：子问题哦o(n) 全局推导o(n)也就是o(n)2

但是这里其实可以优化，也就是子问题这里：

因为是字符串，我们才需要往后遍历找，但是转为数字后，只需要用max比较一下即可，并且用一个数组记录最大值

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型一维数组
     */
    public int[] partitionLabels (String s) {
        // write code here
        int[] str = new int[26];//记录s中每个字符的最大值
        for (int i = 0; i < s.length(); i++) {
            str[s.charAt(i) - 'a'] = i;
        }

        ArrayList<Integer> arr = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, str[s.charAt(i) - 'a']); //一下子便拿到子问题解
            if (i == end) {
                arr.add(end - start + 1);//拿到子串长度
                start = end + 1;
            }
        }
        return arr.stream().mapToInt(Integer::intValue).toArray();
    }
}