Solutions

# Greedy, track the last index of each character. Any character in the current partition must be included in the same partition, so if a character appears later in the string, the current partition must extend at least up to that last occurrence. 
# greedy

# Greedy - O(n) time, O(n) space
# For any character in current partition, we must include all occurrences of that character in this same partition
# so if a character appears later in the string, the current partition must extend at least up to that last occurrence
def partitionLabels(s: str) -> list[int]:
    last_idx = {}
    for i, c in enumerate(s):
        last_idx[c] = i

    curr_partsize = 0
    part_end = 0
    res = []
    for i, c in enumerate(s):
        part_end = max(part_end, last_idx[c])
        curr_partsize += 1

        if part_end == i:
            res.append(curr_partsize)
            curr_partsize = 0
    return res


# Greedy (suboptimal) - O(n^2) time, O(n) space
def partitionLabels1(s: str) -> list[int]:
    last_idx = {}
    for i, c in enumerate(s):
        last_idx[c] = i
    
    curr_partchars = set()
    curr_partsize = 0
    res = []
    for i, c in enumerate(s):
        curr_partchars.add(c)
        curr_partsize += 1

        # if for all characters seen so far
        # we've over their max last index, create a partition
        if all([last_idx[char] <= i for char in curr_partchars]):
            res.append(curr_partsize)
            curr_partchars.clear()
            curr_partsize = 0

    return res