Partition Labels

Problem

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.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

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.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.

Solution

Approach: Greedy with Last Occurrence

The key insight is to track the last occurrence of each character, then greedily extend partitions to include all occurrences of characters seen so far.

Implementation

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # Store last occurrence of each character
        last = {char: i for i, char in enumerate(s)}

        result = []
        start = 0
        end = 0

        for i, char in enumerate(s):
            # Extend partition to include last occurrence of current char
            end = max(end, last[char])

            # If we've reached the end of current partition
            if i == end:
                result.append(end - start + 1)
                start = i + 1

        return result

Approach 2: Alternative Implementation

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

        partitions = []
        partition_start = 0
        partition_end = 0

        for i in range(len(s)):
            partition_end = max(partition_end, last_index[s[i]])

            if i == partition_end:
                partitions.append(partition_end - partition_start + 1)
                partition_start = i + 1

        return partitions

Complexity Analysis

Time Complexity: O(n), where n is length of string. Two passes: one to build last occurrence map, one to create partitions.
Space Complexity: O(1), since we have at most 26 lowercase letters, the hash map has constant size.

Key Insights

Last Occurrence: For each character, we must include its last occurrence in the same partition as its first.
Greedy Extension: As we scan through the string, keep extending the current partition to include last occurrences of all characters seen.
Partition Boundary: When we reach the furthest last occurrence (i == end), we can close the current partition.
Maximum Parts: This greedy approach gives maximum number of partitions because we close each partition as soon as possible.
No Overlap: Once a partition is closed, none of its characters appear in future partitions.
Two-Pass Algorithm: First pass builds the last occurrence map, second pass creates partitions.