原题地址

思考过程:

从最左字符开始,找到该字符在串中的最右位置,然后从左到右遍历字符,依次找到不同字符的最右位置,如果比上一次记录的最右大,更新最右,直到遍历完成后,左到右表示的字符串,即为一个片段,然后把更新最左,一直到遍历完整个串。

代码实现

public List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        int lastP = 0;
        int p = 1;
        Set<Character> set = new HashSet<>();
        while (p <= s.length()) {
            for (int i = lastP; i < p; i++) {
                char c = s.charAt(i);
                if (!set.contains(c)) {
                    int rightPosition = getRightPosition(s, c);
                    p = Math.max(p, rightPosition);
                    set.add(c);
                }
            }
            ans.add(p - lastP);
            lastP = p;
            p++;

        }
        return ans;
    }

    private int getRightPosition(String s, char c) {
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == c) {
                return i + 1;
            }
        }
        return 0;
    }

执行结果:

查看官方解法

贪心算法+双指针(有待深入理解)