763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Return a list of integers representing the size of these parts.

def partitionLabels(s: str):

       

        lastSeen = {c:i for i,c in enumerate(s)}

        j = 0

        anchor = 0

        lengths = []

       

        for i,c in enumerate(s):

            j = max(j, lastSeen[c])

            if i == j:

                lengths.append(i - anchor + 1)

                anchor = i + 1

        return lengths

           

       

       

def partitionLabelsMyFirstAlgo(s: str):

           

    intervals = {}

   

    for i,c in enumerate(s):

        if c not in intervals:

            intervals[c] = (i,i) #inclusive

        intervals[c] = (intervals[c][0], max(intervals[c][1], i))

       

    intervals = list(intervals.values())

    intervals.sort(key=lambda x: x[0])

   

    parts = [intervals[0][1]]

    for interval in intervals[1:]:

        if interval[0] < parts[-1]:

            parts[-1] = max(parts[-1], interval[1])

        else:

            parts.append(interval[1])

           

    lengths = []

    lastP = -1

    for p in parts:

        lengths.append(p-lastP)

        lastP = p

    return lengths