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.

Partition Labels - LeetCode Solution & Explanation

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).

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

The key recognition signals are 'partition string into parts', 'each letter appears in at most one part', and 'maximize number of parts'. These indicate a greedy approach because the problem reduces to finding the earliest point where all characters in the current partition have their last occurrence within the partition. By precomputing last occurrences, the algorithm can greedily extend the current partition's end to the furthest last occurrence of any character seen so far. When the current index reaches this end, a partition is finalized.

Optimal Approach

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.

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.

Solution

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

1

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).

2

Iterate to Build Partitions by Tracking Furthest Last Occurrence

7res = []
8size, end = 0, 0
9for i, c in enumerate(s):
10    size += 1
11    end = max(end, last_index[c])
13    if i == end:
14        res.append(size)
15        size = 0

Objective

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

Key Insight

By updating the partition end to the maximum last occurrence of any character encountered, the algorithm ensures that the partition includes all instances of those characters. When the current index reaches this end, it means the partition is complete and can be recorded.

Interview Quick-Check

Core Logic

The partition boundary is the maximum last occurrence of all characters seen so far; finalizing a partition when the current index equals this boundary ensures no character crosses partitions.

State & Boundaries

Resetting the partition size after appending ensures correct size calculation for subsequent partitions.

Common Pitfalls & Bugs

Failing to update the partition end to the maximum last occurrence can cause premature partitioning and violate the problem's constraints.

3

Return the List of Partition Sizes

17	`return res`

Objective

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

Key Insight

Returning the accumulated partition sizes completes the solution, providing the required output format.

Interview Quick-Check

Core Logic

The result list contains sizes of partitions that satisfy the problem's constraints.

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.

Line 3 Core

last_index = {}

Initialize a dictionary to store the last index of each character.

This dictionary is the foundation for determining partition boundaries by recording where each character last appears in the string.

Line 15 Core

size = 0

Reset the partition size for the next partition.

Resetting size prepares for counting characters in the subsequent partition, ensuring sizes are accurate and independent.

Line 8 Core

size, end = 0, 0

Initialize variables to track current partition size and end boundary.

The size counts characters in the current partition, and end marks the furthest last occurrence of any character seen so far, defining the partition boundary.

Line 14 Core

res.append(size)

Append the current partition size to the result list.

Recording the partition size at this point captures the size of a valid partition that satisfies the problem constraints.

Line 10 Standard

size += 1

Increment the current partition size.

Counting characters ensures accurate partition size measurement for when the partition is finalized.

Line 4 Standard

for i, c in enumerate(s):

Iterate over the string with index and character.

Enumerating the string provides both the character and its position, enabling the update of last occurrence indices.

Line 9 Standard

for i, c in enumerate(s):

Iterate over the string with index and character for partitioning.

This loop processes each character to update partition boundaries and sizes dynamically.

Line 17 Standard

return res

Return the list of partition sizes.

Returning the accumulated partition sizes completes the solution, providing the required output.

Line 7 Basic

res = []

Initialize the result list to store partition sizes.

This list accumulates the sizes of partitions as they are finalized during iteration.

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?

Because the partition boundary is extended to include the last occurrence of every character encountered, ensuring all instances of those characters lie within the partition. Thus, no character can appear beyond this boundary, preventing overlap across partitions.

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`

7	`res = []`
8	`size, end = 0, 0`
9	`for i, c in enumerate(s):`
10	`size += 1`
11	`end = max(end, last_index[c])`
13	`if i == end:`
14	`res.append(size)`
15	`size = 0`

Problem

Example

Approach

Solution

Step-by-Step Solution

Record Last Occurrence of Each Character

Iterate to Build Partitions by Tracking Furthest Last Occurrence

Return the List of Partition Sizes

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.