# 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.
import collections


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

        firstPos, lastPos, posTuple = collections.defaultdict(int), collections.defaultdict(int), {}

        for k, v in enumerate(S):
            if v not in firstPos:
                firstPos[v] = k
            else:
                lastPos[v] = k

        for k in firstPos.keys():
            # bugfixed
            if k not in lastPos:
                lastPos[k] = firstPos[k]
            posTuple[(firstPos[k], lastPos[k])] = k

        res, intervals = [], []

        for b, e in sorted(posTuple.keys()):
            if not intervals:
                intervals.append((b, e))
            else:
                c, d = intervals[-1]
                if b < d:
                    intervals[-1] = (c, max(d, e))
                else:
                    intervals.append((b, e))
                    res.append(d - c + 1)

        res.append(intervals[-1][1] - intervals[-1][0] + 1)
        return res

    def partitionLabels2(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        res = []
        # knowledge see how concise to get the end postion for each char
        ends, start, maxEnd = {c: i for i, c in enumerate(S)}, 0, 0

        for i in xrange(len(S)):
            maxEnd = max(maxEnd, ends[S[i]])
            if i == maxEnd:
                res.append(i - start + 1)
                start = i + 1

        return res





if __name__ == '__main__':
    print Solution().partitionLabels("eaaaabaaec")
    print Solution().partitionLabels2("eaaaabaaec")
    print Solution().partitionLabels("ababcbacadefegdehijhklij")
    print Solution().partitionLabels2("ababcbacadefegdehijhklij")
