package com.fishercoder.solutions;

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

/**
 * 763. Partition Labels
 *
 * A string S of lowercase letters is given.
 * We want to partition this string into as many parts as possible so that each letter appears
 * in at most one part, and return a list of integers representing the size of these parts.

 Example 1:
 Input: S = "ababcbacadefegdehijhklij"
 Output: [9,7,8]
 Explanation:
 The partition is "ababcbaca", "defegde", "hijhklij".
 This is a partition so that each letter appears in at most one part.
 A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

 Note:
 S will have length in range [1, 500].
 S will consist of lowercase letters ('a' to 'z') only.
 */
public class _763 {

  public static class Solution1 {
    public List<Integer> partitionLabels(String S) {
      List<Integer> result = new ArrayList<>();
      int[] last = new int[26];
      /**This is the key step:
       * we find the last occurrence of each letter and record them in last[]*/
      for (int i = 0; i < S.length(); i++) {
        last[S.charAt(i) - 'a'] = i;
      }
      /**record the last end index of the current substring*/
      int end = 0;
      int start = 0;
      for (int i = 0; i < S.length(); i++) {
        end = Math.max(end, last[S.charAt(i) - 'a']);
        if (end == i) {
          result.add(end - start + 1);
          start = end + 1;
        }
      }
      return result;
    }
  }

}

@@ -85,686 +85,8 @@
 t;%0A%0A
-/**%0A * 763. Partition Labels%0A *%0A * A string S of lowercase letters is given.%0A * We want to partition this string into as many parts as possible so that each letter appears%0A * in at most one part, and return a list of integers representing the size of these parts.%0A%0A Example 1:%0A Input: S = %22ababcbacadefegdehijhklij%22%0A Output: %5B9,7,8%5D%0A Explanation:%0A The partition is %22ababcbaca%22, %22defegde%22, %22hijhklij%22.%0A This is a partition so that each letter appears in at most one part.%0A A partition like %22ababcbacadefegde%22, %22hijhklij%22 is incorrect, because it splits S into less parts.%0A%0A Note:%0A S will have length in range %5B1, 500%5D.%0A S will consist of lowercase letters ('a' to 'z') only.%0A */%0A
 publ
@@ -102,16 +102,18 @@
 _763 %7B%0A%0A
+  
   public
@@ -138,16 +138,20 @@
 tion1 %7B%0A
+    
     publ
@@ -201,16 +201,22 @@
 %7B%0A      
+    
+  
 List%3CInt
@@ -249,16 +249,22 @@
 st%3C%3E();%0A
+      
       in
@@ -293,16 +293,22 @@
 ;%0A      
+     
+ 
 /**This 
@@ -324,16 +324,22 @@
 y step:%0A
+      
        *
@@ -412,24 +412,30 @@
 t%5B%5D*/%0A      
+     
+ 
 for (int i =
@@ -453,32 +453,40 @@
 ength(); i++) %7B%0A
+        
         last%5BS.c
@@ -508,26 +508,38 @@
  = i;%0A      
+    
-%7D%0A
+  %7D%0A      
       /**rec
@@ -590,24 +590,30 @@
 ing*/%0A      
+     
+ 
 int end = 0;
@@ -609,24 +609,30 @@
 nt end = 0;%0A
+      
       int st
@@ -636,24 +636,30 @@
  start = 0;%0A
+      
       for (i
@@ -683,32 +683,40 @@
 ength(); i++) %7B%0A
+        
         end = Ma
@@ -761,16 +761,24 @@
         
+    
+    
 if (end 
@@ -795,16 +795,26 @@
         
+         
+ 
 result.a
@@ -834,16 +834,26 @@
 t + 1);%0A
+          
         
@@ -883,18 +883,32 @@
     
+ 
-%7D%0A
+       %7D%0A      
       %7D%0A
     
@@ -899,24 +899,30 @@
           %7D%0A
+      
       return
@@ -934,17 +934,23 @@
 lt;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%0A%7D%0A

refactor 763