Untitled

# this is basically finding and merging intervals:
# 1. we track an interval [x, y] per character c in s where x is the first occurence of c and y is the last occurrence
# 2. we then merge overlapping intervals and return the lengths of each disjoint interval
# the tricky part is ensuring O(n) runtime because normally merge intervals requires some sorting which is O(nlogn)
# however, we can take advantage of the fact that letters appear sequentially and no intervals will ever have the same start point
# this means that the earlier letters will always have distinct start positions and we can use a basic list to track intervals
# any new letter we find will have its interval added to the end of the list (i.e. we open a new interval)
# to ensure O(1) lookup of letters, we have a map from character -> position of its tracked interval in the interval list
#
# O(n) time, O(1) space
# where n is the length of s
# the space complexity of O(1) is because the intervals list scales with the number of distinct letters in s (since we create an interval per distinct character)
# however, since there are only 26 possible characters, the intervals list will always contain between 0 - 26 items
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        if len(s) <= 1:
            return len(s)

        # list of intervals that represent the first and last positions of a letter in s
        intervals = []

        # letter -> its position in the intervals array
        letters_seen = {}

        for i, char in enumerate(s):
            if char in letters_seen:
                # update the end of the interval
                intervals[letters_seen[char]][1] = i
            else:
                intervals.append([i, i])
                letters_seen[char] = len(intervals) - 1

        return [i[1] - i[0] + 1 for i in self.merge_intervals(intervals)]

    def merge_intervals(self, intervals):
        if len(intervals) <= 1:
            return intervals

        result = [intervals[0]]
        for current in range(1, len(intervals)):
            if self.intersects(result[-1], intervals[current]):
                result[-1] = self.merge(result[-1], intervals[current])
            else:
                result.append(intervals[current])

        return result

    def intersects(self, x, y):
        x_start, x_end = x
        y_start, y_end = y

        return (
            (x_start >= y_start and x_start <= y_end)
            or (x_end >= y_start and x_end <= y_end)
            or (y_start >= x_start and y_start <= x_end)
            or (y_end >= x_start and y_end <= x_end)
        )

    def merge(self, x, y):
        return [min(x[0], y[0]), max(x[1], y[1])]