Partition Labels

Problem Description

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]
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

This problem can be solved using a greedy approach with the help of a hash map:

Key Insight

To ensure each letter appears in at most one partition, we need to know the last occurrence of each character in the string. A partition can only end when we've reached the last occurrence of all characters seen so far in the current partition.

Algorithm

1. Record last indices: Create a hash map to store the last occurrence index of each character in the string.
2. Iterate through the string: Use two pointers:
   • start: marks the beginning of the current partition
   • end: marks the farthest last occurrence we've seen so far
3. Extend partition boundary: For each character at index i:
   • Update end to be the maximum of current end and the last occurrence of s[i]
   • If i == end, we've reached the end of the partition (all characters in this partition won't appear later)
4. Record partition size: When i == end, add the partition size (end - start + 1) to the result and update start = i + 1

Greedy Strategy

The greedy choice is to make partitions as early as possible. As soon as we reach a point where we've seen the last occurrence of all characters in the current partition, we immediately create a partition there.

Example Walkthrough

For s = "ababcbacadefegdehijhklij":

1. Last indices: {a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21}
2. Start at index 0 (a), end = 8 (last a)
3. At index 1 (b), end = max(8, 5) = 8
4. Continue until index 8, where i == end, partition size = 9
5. Repeat for remaining characters

Time & Space Complexity

• Time Complexity: O(n) where n is the length of the string (two passes: one to build the map, one to partition)
• Space Complexity: O(1) - the hash map stores at most 26 characters (constant space)

Java Solution

class Solution {
    public List<Integer> partitionLabels(String s) {
        // Record last index of each character
        Map<Character, Integer> lastIndex = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastIndex.put(s.charAt(i), i);
        }

        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            // Update end to the farthest last occurrence
            end = Math.max(end, lastIndex.get(s.charAt(i)));

            // If we've reached the end of the partition
            if (i == end) {
                result.add(end - start + 1);
                start = i + 1;
            }
        }

        return result;
    }
}

Python Solution

def partitionLabels(s: str) -> List[int]:
    # Record last index of each character
    last_index = {char: i for i, char in enumerate(s)}

    result = []
    start, end = 0, 0

    for i, char in enumerate(s):
        # Update end to the farthest last occurrence
        end = max(end, last_index[char])

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

    return result

Visual Example

For s = "ababcbacadefegdehijhklij":

Index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Char:   a b a b c b a c a d e  f  e  g  d  e  h  i  j  h  k  l  i  j
                            |                 |                       |
                         Part 1             Part 2                 Part 3
                      (9 chars)           (7 chars)               (8 chars)

• Part 1: "ababcbaca" - contains {a, b, c} and their last occurrences are all within this partition
• Part 2: "defegde" - contains {d, e, f, g} and their last occurrences are all within this partition
• Part 3: "hijhklij" - contains {h, i, j, k, l} and their last occurrences are all within this partition