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]
    }
}

@@ -61,60 +61,12 @@
 til.
-HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
+List
 ;%0A%0A/
@@ -215,39 +215,24 @@
    List%3C
-Map%3CCharacter, 
 Integer%3E
 %3E list =
@@ -227,13 +227,14 @@
 ger%3E
-%3E lis
+ resul
 t = 
@@ -264,33 +264,32 @@
     
-list.add(new HashMap%3C%3E())
+int%5B%5D last = new int%5B26%5D
 ;%0A  
@@ -318,18 +318,19 @@
 i %3C 
-S
+last
 .length
-()
 ; i+
@@ -350,139 +350,20 @@
     
-char c = S.charAt(i);%0A            for (int j = 0; j %3C list.size(); j++) %7B%0A                Map%3CCharacter, Integer%3E map = list.get(j)
+last%5Bi%5D = -1
 ;%0A  
@@ -364,32 +364,34 @@
 -1;%0A        
+%7D%0A
         
 if (map.cont
@@ -382,182 +382,46 @@
     
-if (map.containsKey(c)) %7B%0A                    map.put(c, map.get(c) + 1);%0A                    int size = list.size();%0A                    for (int k = size
+for (int i = S.length()
  - 1; 
-k
+i
  %3E= 
-j + 1; k
+0; i
 --) 
@@ -438,251 +438,90 @@
     
-            Map%3CCharacter, Integer%3E map2 = list.get(k);%0A                        map2.forEach((key, value) -%3E %7B%0A                            if (map.containsKey(key)) %7B%0A                                map.put(key, map.get(key) + value);%0A        
+if (last%5BS.charAt(i) - 'a'%5D == -1) %7B%0A                last%5BS.charAt(i) - 'a'%5D = i;%0A
     
@@ -524,32 +524,24 @@
             
-        
 %7D%0A          
@@ -534,33 +534,34 @@
   %7D%0A        
- 
+%7D%0A
         
        %7D);%0A 
@@ -552,17 +552,21 @@
     
-       %7D)
+int part = -1
 ;%0A  
@@ -575,221 +575,152 @@
     
-                list.remove(k);%0A                    %7D%0A                    break;%0A                %7D else %7B%0A                    Map%3CCharacter, Integer%3E newMap = new HashMap%3C%3E();%0A                    newMap.put(c, 1);
+int from = 0;%0A        int to = 0;%0A        while (from %3C S.length()) %7B%0A            char c = S.charAt(from);%0A            if (to %3C last%5Bc - 'a'%5D) %7B
 %0A   
@@ -736,34 +736,28 @@
     
-    list.add(newMap);%0A    
+to = last%5Bc - 'a'%5D;%0A
     
@@ -770,33 +770,49 @@
   %7D%0A            
-%7D
+if (from == to) %7B
 %0A        %7D%0A     
@@ -804,26 +804,24 @@
         
-%7D%0A
         
 List%3CInt
@@ -816,203 +816,58 @@
     
-List%3CInteger%3E result = new ArrayList%3C%3E();%0A        for (Map%3CCharacter, Integer%3E map : list) %7B%0A            int total = 0;%0A            for (int value : map.values()) %7B%0A                total += value
+result.add(to - part);%0A                part = from
 ;%0A  
@@ -894,25 +894,14 @@
     
-result.add(total)
+from++
 ;%0A  
@@ -940,192 +940,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem763 prob = new Problem763();%0A        System.out.println(prob.partitionLabels(%22ababcbacadefegdehijhklij%22)); // %5B9,7,8%5D%0A    %7D
 %0A%7D%0A

Solve problem 763