LeetEye LeetEye
Medium Greedy ~5 min

Partition Labels

greedy 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.

Examples

Example 1
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
"ababcbaca", "defegde", "hijhklij"
Example 2
Input: s = "eccbbbbdec"
Output: [10]
Key Insight

A partition must include ALL occurrences of any character it contains.

Track last occurrence of each char. Extend partition end to max(end, last[current_char]). When index equals end, close partition.

How to Approach This Problem

Pattern Recognition: When you see keywords like partition labels greedy, think Greedy.

Step-by-Step Reasoning

1 If partition contains character 'a', it must:
Answer: Contain ALL occurrences of 'a'
Each character appears in at most one part, so all its occurrences must be together.
2 For each character, we need:
Answer: Last occurrence
Partition containing a character must extend at least to its last occurrence.
3 As we traverse, we extend current partition to:
Answer: Last occurrence of current char
If we see char c, we must include everything up to c's last occurrence.
4 We can close the current partition when:
Answer: Current index equals the partition's farthest required extent
If i == end, all characters in this partition have been fully included.
5 The partition end is updated to:
Answer: max(end, last[s[i]])
End grows to accommodate all characters. Take max with current end.

Solution

def partitionLabels(s: str) -> List[int]:
    # Find last occurrence of each character
    last = {c: i for i, c in enumerate(s)}
    
    result = []
    start = 0
    end = 0
    
    for i, c in enumerate(s):
        end = max(end, last[c])  # Extend partition
        
        if i == end:  # All chars in partition fully included
            result.append(end - start + 1)
            start = i + 1
    
    return result

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye