How do you solve Partition Labels?

First, map each character to its last index in the string. Then iterate through the string, updating the current partition's end to the maximum last occurrence of characters encountered. When the current index equals the end, append the partition size to the result and reset the size counter. This greedy approach guarantees the maximum number of partitions with the required property.

Partition Labels

Q: What is the time complexity of Partition Labels?

O(n). The algorithm makes two passes over the string: one to record last occurrences and one to partition, each O(n). All operations inside loops are O(1).

Q: What pattern does Partition Labels use?

The Pattern: Greedy Algorithms (Interval Partitioning) The Heuristic: When partitioning a sequence to satisfy a global constraint on element occurrences, track the furthest required boundary for all elements seen so far and finalize partitions at the earliest point where the current index meets this boundary.

Medium Greedy Algorithms

Problem

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

1 ≤ s.length ≤ 500
s consists of lowercase English letters only.

Example

Input: s = "ababcbacadefegdehijhklij"

Output: [9,7,8]

The algorithm first records the last index of each character: for example, 'a' last appears at index 8, 'b' at 5, 'c' at 7, etc. Then it iterates through the string, tracking the furthest last occurrence of any character seen so far (the 'end'). When the current index reaches this 'end', it means all characters in the current partition appear only within this range. The partition size is recorded (end - start + 1), and the process repeats from the next index. For the input, the partitions are [0..8], [9..15], and [16..23], with sizes 9, 7, and 8 respectively.

Approach

Straightforward Solution

A brute-force approach would try all possible partitions and check if characters repeat across partitions, which is exponential and infeasible.

Core Observation

Each character's last occurrence in the string defines a boundary that any partition containing that character must at least extend to. The partition boundary is the maximum last occurrence of all characters seen so far in the current partition.

Path to Optimal

Preview

The key recognition signals are 'partition string into parts', 'each letter appears in at most one part', and 'maximize number of parts'…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

First, map each character to its last index in the string. Then iterate through the string, updating the current partition's end to the maximum last occurrence of characters encountered…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes two passes over the string: one to record last occurrences and one to partition, each O(n). All operations inside loops are O(1).

Space

O(1)

The last occurrence map stores at most 26 entries for lowercase English letters, which is constant space. The output list scales with the number of partitions but is required by the problem.

Pattern Spotlight

Greedy Algorithms (Interval Partitioning)

When partitioning a sequence to satisfy a global constraint on element occurrences, track the furthest required boundary for all elements seen so far and finalize partitions at the earliest point where the current index meets this boundary.

Solution

Python

1class Solution:
  def partitionLabels(self, s: str) -> list[int]:
      last_index = {}
      for i, c in enumerate(s):
          last_index[c] = i
      
      res = []
      size, end = 0, 0
      for i, c in enumerate(s):
          size += 1
          end = max(end, last_index[c])
12
          if i == end:
              res.append(size)
              size = 0
      
      return res

Step-by-Step Solution

Record Last Occurrence of Each Character

3last_index = {}
4for i, c in enumerate(s):
5    last_index[c] = i

Objective

To map each character in the string to its last index of appearance.

Key Insight

Knowing the last occurrence of each character is essential because it defines the minimum boundary any partition containing that character must reach. This precomputation enables the greedy extension of partition boundaries in a single pass.

Interview Quick-Check

Core Logic

Mapping characters to their last indices allows constant-time lookup of partition boundaries during iteration.

Complexity

This step is O(n) time and O(1) space since the character set is fixed (lowercase English letters).

Iterate to Build Partitions by Tracking Furthest Last Occurrence

To traverse the string and dynamically update the current partition's end boundary based on characters seen.

Return the List of Partition Sizes

To output the computed list of partition sizes after processing the entire string.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 11 Critical

end = max(end, last_index[c])

Update the partition end to the maximum last occurrence of characters seen.

Extending the partition boundary to the furthest last occurrence guarantees that all instances of characters in the partition are included, preventing overlap with future partitions.

Line 5 Critical

last_index[c] = i

Update the last occurrence of the current character.

Assigning the current index as the last occurrence ensures the dictionary always holds the furthest position for each character.

Line 13 Critical

if i == end:

Check if the current index matches the partition end boundary.

When the current index reaches the partition end, it signifies that all characters in the partition are contained within this range, allowing the partition to be finalized.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does finalizing a partition when the current index reaches the maximum last occurrence of all characters seen so far guarantee that no character appears in multiple partitions?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Partition Labels from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Partition Labels drill

or drill a free problem

1	`class Solution:`
2	`def partitionLabels(self, s: str) -> list[int]:`
3	`last_index = {}`
4	`for i, c in enumerate(s):`
5	`last_index[c] = i`
6
7	`res = []`
8	`size, end = 0, 0`
9	`for i, c in enumerate(s):`
10	`size += 1`
11	`end = max(end, last_index[c])`
12
13	`if i == end:`
14	`res.append(size)`
15	`size = 0`
16
17	`return res`