"""Leetcode 763. Partition Labels
Medium

URL: https://leetcode.com/problems/partition-labels/submissions/

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.
"""

class SolutionDict(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]

        Time complexity: O(n).
        Space complexity: O(n).
        """
        from collections import defaultdict

        partition_lens = []

        # Use dict to record last index.
        last_idx = defaultdict(int)

        for i, c in enumerate(S):
            last_idx[c] = i

        # Iterate from index 0 to check end indeces and partion.
        i = 0
        while i < len(S):
            end_idx = last_idx[S[i]]

            # Start from index i to update their end indeces.
            j = i
            while j < end_idx:
                end_idx = max(end_idx, last_idx[S[j]])
                j += 1

            partition_lens.append(j - i + 1)
            i = j + 1

        return partition_lens


def main():
    S = "ababcbacadefegdehijhklij"
    print SolutionDict().partitionLabels(S)


if __name__ == '__main__':
    main()

@@ -983,29 +983,24 @@
         part
-ition
 _lens = %5B%5D%0A%0A
@@ -1033,21 +1033,35 @@
 rd last 
-index
+pos for each letter
 .%0A      
@@ -1067,19 +1067,21 @@
    last_
-idx
+poses
  = defau
@@ -1092,17 +1092,16 @@
 ct(int)%0A
-%0A
         
@@ -1143,19 +1143,21 @@
    last_
-idx
+poses
 %5Bc%5D = i%0A
@@ -1169,253 +1169,337 @@
     
-# Iterate from index 0 to check end indeces and partion.%0A        i = 0%0A        while i %3C len(S):%0A            end_idx = last_idx%5BS%5Bi%5D%5D%0A%0A            # Start from index i to update their end indeces.%0A            j = i%0A            while j %3C end_idx:
+i = 0%0A        while i %3C len(S):%0A            # For each letter, get its last position.%0A            end_pos = last_poses%5BS%5Bi%5D%5D%0A%0A            j = i%0A            while j %3C end_pos:%0A                # Interate through each letter following S%5Bi%5D, update last position.%0A                # If j is out of last position, we get one partition.
 %0A   
@@ -1515,19 +1515,19 @@
     end_
-idx
+pos
  = max(e
@@ -1533,21 +1533,23 @@
 end_
-idx
+pos
 , last_
-idx
+poses
 %5BS%5Bj
@@ -1588,29 +1588,24 @@
         part
-ition
 _lens.append
@@ -1616,16 +1616,81 @@
  i + 1)%0A
+            # Start from the next of the previous partition end.%0A
         
@@ -1723,21 +1723,16 @@
 urn part
-ition
 _lens%0A%0A%0A

Refactor codes and add comments