Partition Labels

LeetCode 763: Partition Labels Solution & Explanation

Problem Overview

TL;DR: Record the last position of every character, scan the string from left to right, and close a partition only when the current index reaches the farthest required last occurrence.

The LeetCode 763 Solution divides s into contiguous parts such that every character appears in only one part. If a character appears multiple times, all of its occurrences must remain inside the same partition. Among all valid partitions, the goal is to return the one with the maximum number of parts.

For example, in "abac", the two occurrences of a force the first partition to extend through index 2, producing [3, 1].

This is a popular interview question because it tests whether a greedy boundary can be derived from future occurrence information. The optimal solution for interviews runs in linear time.

Brute Force Approach for Partition Labels

A direct approach is to repeatedly construct a candidate partition and verify whether every character inside it has all of its occurrences within that partition.

One possible naive strategy is:

1. Start a partition at the current unprocessed index.
2. Extend the partition one character at a time.
3. After every extension, scan the candidate substring.
4. Check whether any character appears later outside the candidate.
5. If the candidate is valid, continue from the next index.
6. Select the partitioning with the greatest number of valid parts.

Naive Pseudocode

function partitionLabelsBruteForce(s):
    bestPartition = empty list

    search(start, currentPartition):
        if start == length(s):
            update bestPartition if currentPartition has more parts
            return

        for end from start to length(s) - 1:
            if every character in s[start..end] has no occurrence after end:
                add end - start + 1 to currentPartition
                search(end + 1, currentPartition)
                remove the last size

    search(0, [])
    return bestPartition

A simpler greedy-looking brute force implementation that repeatedly rescans suffixes still performs poorly:

• It may examine many possible ending positions.
• Each candidate can require scanning a large portion of the string.
• Repeated checks can result in O(n²) or worse behavior.
• Exploring all valid partition combinations can be exponential in the worst case.

With n up to 10^5, this approach can result in Time Limit Exceeded. The main issue is that it repeatedly recomputes character occurrence information instead of maintaining a boundary derived from the entire input.

Algorithm Strategy: Greedy Patterns

1. Build an array or map containing the last index of every character.
2. Initialize:
   • partitionStart = 0
   • partitionEnd = 0
   • an empty result list
3. Sweep through the string from left to right.
4. For each character:
   • Look up its last occurrence.
   • Update partitionEnd to the larger of its current value and that last occurrence.
5. When the current index equals partitionEnd:
   • The current partition is complete.
   • Add its length to the result.
   • Set the next partition start to the following index.
6. Return the partition sizes.

The boundary never moves backward. Each partition is closed at the earliest index where it is safe to do so.

Execution Flow

For s = "qrrqst":

1. Precompute last occurrences:
   • q -> 3
   • r -> 2
   • s -> 4
   • t -> 5
2. Start with partitionStart = 0 and partitionEnd = 0.
3. At index 0, character q requires index 3, so partitionEnd = 3.
4. At index 1, character r requires index 2; the boundary remains 3.
5. At index 2, character r does not extend the boundary.
6. At index 3, character q ends at index 3. Since the scan has reached partitionEnd, close the first partition:
   • Size: 3 - 0 + 1 = 4
   • New partitionStart = 4
7. At index 4, character s requires index 4, so the boundary is 4.
8. Since the current index equals the boundary, close a partition of size 1.
9. At index 5, character t requires index 5, so close another partition of size 1.
10. Return [4, 1, 1].

Proof of Correctness

We prove that the algorithm returns the unique partition with the maximum possible number of parts.

Invariant

During the scan of a current partition beginning at partitionStart, partitionEnd equals the maximum last occurrence of every character encountered since partitionStart.

This holds initially because partitionEnd is updated with the last occurrence of each scanned character. Taking the maximum preserves the invariant after every step.

Validity of Each Closed Partition

Suppose the algorithm closes a partition at index i, where i == partitionEnd.

For every character inside the partition:

• Its last occurrence was included when that character was scanned.
• partitionEnd is at least that last occurrence.
• Since partitionEnd == i, the character has no occurrence after i.

Therefore, every occurrence of every character in the partition lies within the partition. The partition is valid.

No Earlier Boundary Is Valid

Before reaching partitionEnd, the scan index is less than the last occurrence of at least one character already in the partition. Closing earlier would place that character's later occurrence in a different partition, violating the requirement that all copies of a character stay together.

Thus, no valid partition boundary can occur before partitionEnd.

Maximum Number of Partitions

The algorithm closes each partition at the earliest valid boundary. Any valid solution must end its first partition at or after this boundary. Choosing the earliest valid boundary leaves the longest possible suffix for subsequent partitions.

Applying the same argument to each remaining suffix shows that every partition is also closed as early as possible. Therefore, the algorithm produces the greatest possible number of valid partitions.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 759: Employee Free Time
• LeetCode 986: Interval List Intersections

In Employee Free Time, a line sweep tracks active interval boundaries and identifies gaps where no interval is active. In Interval List Intersections, two ordered interval boundaries are advanced according to the smaller endpoint. Both problems use left-to-right boundary movement to maintain interval constraints, similar to the active partitionEnd in LeetCode 763: Partition Labels.

Reference Implementation

C++ Solution for LeetCode 763

1class Solution {
2public:
3    vector<int> partitionLabels(string s) {
4        vector<int> last(26, -1);
5        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
6            last[s[i] - 'a'] = i;
7        }
8
9        vector<int> result;
10        int partitionStart = 0;
11        int partitionEnd = 0;
12
13        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
14            partitionEnd = max(partitionEnd, last[s[i] - 'a']);
15            if (i == partitionEnd) {
16                result.push_back(i - partitionStart + 1);
17                partitionStart = i + 1;
18            }
19        }
20
21        return result;
22    }
23};

The last array stores the final index of each lowercase letter. During the sweep, partitionEnd is extended whenever the current character requires a farther endpoint.

Java Solution for LeetCode 763

1class Solution {
2    public int[] partitionLabels(String s) {
3        int[] last = new int[256];
4        for (int i = 0; i < s.length(); i++) {
5            last[s.charAt(i)] = i;
6        }
7
8        java.util.List<Integer> result = new java.util.ArrayList<>();
9        int start = 0;
10        int end = 0;
11
12        for (int i = 0; i < s.length(); i++) {
13            end = Math.max(end, last[s.charAt(i)]);
14            if (i == end) {
15                result.add(i - start + 1);
16                start = i + 1;
17            }
18        }
19
20        int[] answer = new int[result.size()];
21        for (int i = 0; i < result.size(); i++) {
22            answer[i] = result.get(i);
23        }
24        return answer;
25    }
26}

The Java implementation uses a fixed-size array indexed by character code. The start and end variables represent the current active partition boundaries.

Python Solution for LeetCode 763

1class Solution:
2    def partitionLabels(self, s: str) -> List[int]:
3        last = {char: index for index, char in enumerate(s)}
4        result = []
5        start = 0
6        end = 0
7
8        for index, char in enumerate(s):
9            end = max(end, last[char])
10            if index == end:
11                result.append(index - start + 1)
12                start = index + 1
13
14        return result

The dictionary comprehension computes each character's last position. The sweep then maintains the same greedy boundary invariant as the C++ and Java versions.