loading

Partition Labels — Step-by-Step Visualization

mediumLeetCode #763StringHash TableGreedyTwo Pointers

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.

Algorithm Pattern

Greedy / Last Occurrence Map

Key Idea

To ensure a character appears in only one part, that part must extend at least to the character's last occurrence in the string. As we iterate, we maintain the `end` of the current partition, which is the maximum of the 'last occurrences' of all characters encountered so far. When the current index `i` catches up to `end`, we have found a valid partition.

Step-by-Step Approach

  1. Create a map `last` where `last[c]` is the last index of character `c` in `s`.
  2. Initialize `start = 0` and `end = 0`.
  3. For `i, c` in `enumerate(s)`:
  4. Update `end = max(end, last[c])`.
  5. If `i == end`:
  6. The current partition is complete. Add `i - start + 1` to results.
  7. Update `start = i + 1`.
  8. Return results.

Common Gotchas

  • The goal is 'as many parts as possible', which greedy naturally solves by closing a partition as soon as `i == end`.

Related Problems

← All problems