LC763 Partition Labels

class Solution:
    # time O(N) where N=26 ~ O(1) space O(1)
    """
    main idea: for each char, store their last appeared index, then loop through each char,keep updating biggest last index, and  check if any of them has reached biggest last index so far. 
    
    """
    def partitionLabels(self, S: str) -> List[int]:
        if S == "":
            return []
        res = []
        last = {c:i for i,c in enumerate(S)}
        start = end = 0
        for i,c in enumerate(S):
            print(end,last[c])
            end = max(end,last[c])
            if i == end:
                res.append(end-start+1)
                start = end +1
        return res