Partition Labels

Difficulty: Medium

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.

Return a list of integers representing the size of these parts.

Example

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Explanation: The partition is 'ababcbaca', 'defegde', 'hijhklij'. Each letter appears in at most one part. For example, 'a' appears only in the first part, 'd' and 'e' only in the second part.

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)