763. Partition Labels

https://leetcode.com/problems/partition-labels/

Python

Greedy

• Time: O(N)
• Space: O(N)

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_seem = {char: index for index, char in enumerate(s)}

        start, end = 0, 0

        ans = []
        for index, char in enumerate(s):
            end = max(end, last_seem[char])
            if index == end:
                ans.append(end+1 - start)
                start = index + 1

        return ans

Or, you'd like to see what those partitions are

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_seem = {char: index for index, char in enumerate(s)}

        start, end = 0, 0
        partitions = []
        for index, char in enumerate(s):
            end = max(end, last_seem[char])
            if index == end:
                partitions.append(s[start:end+1])
                start = index + 1

        return [len(part) for part in partitions]