Partition Labels

Difficulty: Medium

Problem

You are given a string s. Cut it into consecutive pieces so that no letter shows up in more than one piece, and make the number of pieces as large as you can.

Return the lengths of the pieces, in order, as a list of integers.

Example

Input: s = "abacdcefeg"
Output: [3, 3, 3, 1]
Explanation: The pieces are 'aba', 'cdc', 'efe' and 'g'. No letter appears in two pieces; for example 'c' and 'd' stay inside the second piece, and cutting any of these pieces further would split a repeated letter across two pieces.

Brute-force approach

For each possible partition point, check if all characters before appear only before.

Steps

  1. For each position i, check if it's a valid partition point
  2. A valid point means all characters in [start, i] don't appear after i
  3. If valid, record partition size and continue
  4. This requires checking each character's occurrences

Time complexity: O(n² × k) · Space complexity: O(k)

Trade-offs

  • Repeatedly scans string for each character
  • O(n²) positions × O(k) character checks
  • Can precompute last indices to avoid repeated scans

Optimal approach

Key insight: A partition must include all occurrences of every character it contains. Precompute last index of each char, then extend partition to include all required characters.

Precompute last occurrence of each character, then greedily extend partitions.

Steps

  1. Pass 1: Build hash map of last occurrence for each character
  2. Pass 2: For each character, extend 'end' to its last occurrence
  3. When current index i reaches 'end', partition is complete
  4. Record partition size and start new partition

Time complexity: O(n) · Space complexity: O(k)

Pseudocode

function partitionLabels(s):
    // Step 1: Record last occurrence of each character
    last = {}
    for i from 0 to len(s):
        last[s[i]] = i
    
    // Step 2: Greedily extend partitions
    result = []
    start = 0, end = 0
    
    for i from 0 to len(s):
        end = max(end, last[s[i]])
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    
    return result

Hints

  • First, find the last index of each character
  • Use a greedy approach to extend partitions
  • A partition ends when i reaches the farthest last occurrence

Complexity questions

Time for brute force approach?

O(n² × k). O(n) positions × O(n) substring × O(k) character check.

Time for greedy + hash map approach?

O(n). Two passes through the string, each O(n).

Space for greedy approach?

O(k) where k = alphabet size. Hash map stores at most k (26 for lowercase) entries.

Why do we need two passes in the optimal solution?

First finds last occurrences, second creates partitions. We need to know the last occurrence before we can determine partition boundaries.

Check your understanding of Partition Labels

What constraint must each partition satisfy?

Each letter appears in at most one partition. No letter can appear in multiple partitions.

For 'ababcbacadefegdehijhklij', why can't we split after 'ab'?

'a' appears later in the string. 'a' appears at index 8 too, so partition must include at least indices 0-8.

What's the goal for number of partitions?

Maximize (as many as possible). We want as many parts as possible while satisfying the constraint.

Related problems

Keep practising