package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/partition-labels/
 */
public class Problem763 {
    public List<Integer> partitionLabels(String S) {
        List<Map<Character, Integer>> list = new ArrayList<>();
        list.add(new HashMap<>());
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            for (int j = 0; j < list.size(); j++) {
                Map<Character, Integer> map = list.get(j);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                    int size = list.size();
                    for (int k = size - 1; k >= j + 1; k--) {
                        Map<Character, Integer> map2 = list.get(k);
                        map2.forEach((key, value) -> {
                            if (map.containsKey(key)) {
                                map.put(key, map.get(key) + value);
                            }
                        });
                        list.remove(k);
                    }
                    break;
                } else {
                    Map<Character, Integer> newMap = new HashMap<>();
                    newMap.put(c, 1);
                    list.add(newMap);
                }
            }
        }
        List<Integer> result = new ArrayList<>();
        for (Map<Character, Integer> map : list) {
            int total = 0;
            for (int value : map.values()) {
                total += value;
            }
            result.add(total);
        }
        return result;
    }

    public static void main(String[] args) {
        Problem763 prob = new Problem763();
        System.out.println(prob.partitionLabels("ababcbacadefegdehijhklij")); // [9,7,8]
    }
}

package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/partition-labels/
 */
public class Problem763 {
    public List<Integer> partitionLabels(String S) {
        List<Integer> result = new ArrayList<>();
        int[] last = new int[26];
        for (int i = 0; i < last.length; i++) {
            last[i] = -1;
        }
        for (int i = S.length() - 1; i >= 0; i--) {
            if (last[S.charAt(i) - 'a'] == -1) {
                last[S.charAt(i) - 'a'] = i;
            }
        }
        int part = -1;
        int from = 0;
        int to = 0;
        while (from < S.length()) {
            char c = S.charAt(from);
            if (to < last[c - 'a']) {
                to = last[c - 'a'];
            }
            if (from == to) {
                result.add(to - part);
                part = from;
            }
            from++;
        }
        return result;
    }
}

Solve problem 763