Partition Labels LeetCode 763 Guide

LeetCode 763 — Partition Labels — gives you a string s and asks you to partition it into as many parts as possible such that each letter appears in at most one part. Return a list of integers representing the size of each part.

The partition must cover the entire string from left to right. Every character that appears in one partition must not appear in any other partition. The goal is to maximize the number of partitions while satisfying this constraint.

This problem is a classic greedy exercise. The key observation is that a character forces the current partition to extend at least to its last occurrence in the string. By tracking last occurrences and expanding boundaries greedily, we can solve it in linear time.

The first step is to scan the entire string and record the last index where each character appears. This takes O(n) time and O(1) space since there are at most 26 lowercase letters. We store these in a hash map or array of size 26.

For example, in the string "ababcbacadefegdehijhklij", the character a last appears at index 8, b at index 5, c at index 7, and so on. This map is the foundation of the greedy decision — it tells us the farthest point the current partition must reach to include all occurrences of characters we have already seen.

Building this map before the main pass is essential. Without knowing where each character ends, we cannot determine when it is safe to cut a partition. This preprocessing step converts a potentially complex problem into a simple single-pass greedy scan.

With the last occurrence map in hand, we make a single left-to-right pass through the string. We maintain two variables: partitionEnd (the farthest last occurrence seen so far in the current partition) and partitionStart (the start index of the current partition).

For each index i, we update partitionEnd to be the maximum of partitionEnd and the last occurrence of s[i]. This expansion ensures that every character encountered so far will have all its occurrences within the current partition.

When i equals partitionEnd, we have reached the boundary where all characters in the current partition have their last occurrence at or before this index. At this point we record the partition size as partitionEnd - partitionStart + 1, then start a new partition at i + 1.

Consider s = "ababcbacadefegdehijhklij". First build the last occurrence map: a→8, b→5, c→7, d→14, e→15, f→11, g→13, h→19, i→22, j→23, k→20, l→21.

Start scanning: i=0, char a, partitionEnd = max(0, 8) = 8. At i=1, char b, partitionEnd = max(8, 5) = 8. Continue — partitionEnd stays 8 through characters a, b, c. At i=8, i equals partitionEnd, so cut: partition size = 8 - 0 + 1 = 9.

New partition starts at i=9. char d, partitionEnd = 14. Continue expanding through e(15), f(11), g(13). At i=15, i equals partitionEnd, cut: size = 15 - 9 + 1 = 7. Final partition starts at 16, expands through h(19), i(22), j(23), k(20), l(21). At i=23, cut: size = 23 - 16 + 1 = 8. Result: [9, 7, 8].

In Python, the implementation is concise. Use a dictionary comprehension to build the last occurrence map, then iterate with enumerate tracking partitionEnd and partitionStart. When i equals partitionEnd, append the partition size and update partitionStart.

In Java, use an int array of size 26 for the last occurrence map. The logic is identical: scan once to build the map, scan again to greedily expand and cut partitions. The result is collected in an ArrayList<Integer>.

Both implementations run in O(n) time with O(1) extra space. The two passes over the string are each linear. The space for the last occurrence map is bounded by the alphabet size (26), which is constant.

Time complexity is O(n) where n is the length of the string. We make exactly two passes: one to build the last occurrence map and one to partition. Each pass is linear and performs constant work per character.

Space complexity is O(1). The last occurrence map stores at most 26 entries for lowercase English letters. The output list stores at most n entries in the worst case (every character is unique), but this is considered part of the output rather than auxiliary space.

This is optimal — we must read every character at least once, so O(n) time is a lower bound. No sorting or complex data structures are needed, making this one of the most elegant greedy solutions in the LeetCode catalog.

Partition Labels shares its core idea with several other greedy interval problems. Merge Intervals and Insert Interval both require tracking and expanding boundaries, though they operate on explicit intervals rather than implicit ones derived from character positions.

The Jump Game family (LeetCode 45, 55) also uses greedy boundary expansion: track the farthest reachable index and decide when to take the next jump. The structural similarity — expand a boundary, act when reached — makes these problems excellent practice companions.

Another close relative is the Minimum Number of Arrows to Burst Balloons (LeetCode 452), where you greedily find overlapping intervals. Mastering partition labels builds transferable intuition for all these boundary-expansion greedy problems.