763. Partition Labels - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given a string s consisting of lowercase English letters. Your task is to partition s into as many contiguous parts as possible such that each letter appears in at most one part. After partitioning, concatenating all parts in order should yield the original string. The output should be a list of integers representing the size (length) of each part.

Examples:

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
Explanation: The string can be partitioned as "ababcbaca", "defegde", "hijhklij". Each letter appears in only one part. For instance, all occurrences of a, b, and c are in the first part, etc. A partition like "ababcbacadefegde", "hijhklij" would be invalid because it results in fewer parts (some letters would span across parts).
Input: s = "eccbbbbdec"
Output: [10]
Explanation: The entire string is one part (length 10). It cannot be split into smaller parts without repeating letters across parts. Any cut would cause at least one letter to appear in both partitions.
Input: s = "abac"
Output: [3, 1]
Explanation: One optimal partition is ["aba", "c"] yielding lengths [3, 1]. All occurrences of a and b are contained in the first substring "aba", and c stands alone in the second. This ensures no letter appears in more than one part. If we tried to cut earlier (e.g. after "ab"), the letter a would appear in both parts, which is not allowed.

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters ('a' to 'z' only).

Hints

Hint 1: If you cut the string at an index, what condition must be true for that cut to be valid? Think about the letters in the left part – none of those letters should appear in the remainder of the string.
Hint 2: It may help to know the last index at which each character appears. If you know a character’s final occurrence in s, you can decide where a partition should end.
Hint 3: Try a greedy strategy: scan the string and expand the current partition until you’ve included the last occurrence of all letters seen so far. When you reach a point where the current index is the furthest last-occurrence among those letters, you can cut the partition.

Brute Force Approach

A straightforward approach is to build partitions one by one from the start of the string, checking at each potential cut if the partition is valid. The idea is to extend a partition until all letters in that part do not appear later in the string.

Approach: Start at the beginning of s and gradually increase the partition end index until the partition is self-contained. For a given partition ending at index j, ensure that no character in s[start...j] appears in s[j+1...]. If this condition is met, we finalize a partition at j and then repeat the process for the next part starting at j+1. If the condition is not met, we keep extending the partition.
Example (Brute Force): Consider s = "abac". Start with the first character:
- Extend to include a and b ("ab"). We check if any of these letters reappear later. The letter a appears again at index 2, so we cannot cut at index 1.
- Extend to index 2 ("aba"). Now the letters a and b in this segment do not appear after index 2 (the last a is at 2, last b is at 1). This is a valid cut. We record a partition of length 3.
- Start the next part from index 3. "c" by itself has no repeating letters elsewhere, so we cut here. Partition length 1.
  The result is partitions of lengths [3, 1], matching the expected output.

Implementation (Python):

We can implement the brute force by scanning for each possible cut. In the code below, for each expanding segment we use a set to track letters and verify if all those letters have their last occurrence within the segment before cutting.

Python3

. . . .

Implementation (Java):

The brute force approach in Java similarly expands a partition and checks validity by ensuring no character crosses the boundary.

Java

. . . .

Time Complexity: This brute force method is less efficient. In the worst case, verifying each potential cut requires scanning the remaining characters, resulting in roughly quadratic time, O(n²) (given the constraint n <= 500, this is manageable).
Space Complexity: O(n) in the worst case for data structures used (such as the set of seen characters and the result list). The number of distinct letters is at most 26, so the space for tracking characters is effectively O(1).

Optimized Approach

The optimal solution uses a greedy strategy with the help of character last occurrence indices. The key insight is that if you know the last position of each character in the string, you can determine the boundaries of each partition in one pass.

Strategy: First, scan the string to record the last index of each character in a dictionary or array. Then iterate through the string, expanding a window for the current partition. Maintain a pointer current_end that tracks the farthest last-occurrence index among all characters in the current partition. As you move through the string:

Add the current character’s last index to the consideration by updating current_end = max(current_end, lastIndex[current_char]).
If the current index i reaches current_end, it means all characters seen so far in this partition end by this index and do not appear later. At this point, cut the partition. Record the partition size i - partition_start + 1 and start a new partition from the next index.

Using this approach, each character is processed once (to update the farthest boundary), and each partition is finalized exactly at the point where it satisfies the condition.

Example (Greedy): For s = "ababcbacadefegdehijhklij":
Compute last occurrences:
a:8, b:5, c:7, d:14, e:15, f:11, g:13, h:19, i:22, j:23, k:20, l:21 (others letters not present).
Now iterate through s and expand partitions:
- From index 0, the first letter is a (last index 8). current_end = 8. As we go to index 1 (b with last 5), current_end stays 8 (since 8 > 5). Index 2 (a again) doesn't change current_end. Index 3 (b again) no change. Index 4 (c with last 7) keeps current_end = 8. Indices 5 (b), 6 (a), 7 (c) all still within the range. When we reach index 8, current_end is 8 and i == current_end. We cut a partition of length 8 - 0 + 1 = 9.
- The next partition starts at index 9 (d with last 14). We update current_end = 14. Move through indices 10 (e last 15 → now current_end = 15), 11 (f last 11), 12 (e), 13 (g last 13), 14 (d). At index 15 (e), we have reached current_end = 15 (i == current_end), so cut partition of length 15 - 9 + 1 = 7.
- Finally, partition from index 16 to 23 yields length 8. This matches the output [9,7,8].

Implementation (Python):

We use a single pass to determine partitions greedily. This approach leverages the precomputed last indices to run in linear time.

Python3

. . . .

Implementation (Java):

This solution uses an array of size 26 for last indices (since s has lowercase letters). We then iterate and partition greedily.

Java

. . . .

Time Complexity: O(n). We make one pass to compute last occurrences and another pass to form partitions, each linear in the length of the string.
Space Complexity: O(1) additional space (the last-index array has a fixed size of 26, and the output list at most 26 entries long in the worst case). The approach primarily uses constant extra space beyond the input and output.

Edge Cases and Common Mistakes

Single character string: e.g. s = "a" should output [1]. The algorithm should handle length-1 input by returning a single partition of size 1.
All characters the same: e.g. s = "bbbb" should output [4]. Since one letter spans the entire string, only one partition is possible.
No repeating characters: e.g. s = "abcd" should output [1, 1, 1, 1]. Every character can be its own partition because no letter repeats later.
Letters spanning entire string: If one character’s last occurrence is at the end of the string, it will force the first partition to extend to the end (resulting in a single partition). For example, in "aba", the letter a spans from index 0 to 2, so the output is [3] (not [2,1] or similar).
Common Pitfall – Misinterpreting the condition: Remember that letters can repeat within the same part. The rule is that a letter should not appear in two different parts. For instance, "aba" is a valid single partition even though a appears twice, because those a's are in one part. A mistake is trying to cut the string whenever you see a repeated letter – that would violate the condition if that letter appears again later.
Off-by-one errors: When implementing, be careful when calculating partition lengths and updating start indices. A common mistake is forgetting to reset the partition start after adding a partition, or miscomputing the length (it should be end_index - start_index + 1).
Not capturing the last partition: Ensure that after the final index is processed (or the loop ends), the last partition length is recorded. In the greedy approach, this naturally happens when i == current_end at the end of the string.

Alternative Variations

Different Characters Domain: If s included uppercase letters or other characters, the solution approach remains the same. You would simply adjust the storage for last occurrences (e.g., use a larger array or a hashmap for characters). The logic of partitioning by last index does not change.
Partitioning an Array: A similar problem can be posed for arrays of integers: partition an array into maximum segments such that each distinct number appears in at most one segment. The approach would be analogous – find the last index of each number and then partition greedily using those last indices.
Substrings with Unique Letters: A twist is to partition a string such that each part has all distinct letters (no duplicate letters even within a part). This is a different problem – here you would cut whenever you are about to repeat a letter. The strategy would involve using a set to track letters in the current substring and starting a new partition whenever a duplicate is encountered.
Selective Substring Extraction: Another variation: find the maximum number of non-overlapping substrings (not necessarily covering the whole string) such that each letter appears in at most one of the chosen substrings. This is a more complex problem (LeetCode 1520) that builds on the same idea of using last occurrences, but requires careful selection of segments since you don’t have to cover the entire string.

LeetCode 769: Max Chunks To Make Sorted – Partition an array into the maximum number of “sorted” chunks. The greedy approach of splitting when a condition on the max index/value is met is analogous to how we split when reaching the furthest needed index in Partition Labels.
LeetCode 131: Palindrome Partitioning – Although the condition is different (partitions must be palindromes), it’s another string partitioning problem. It contrasts with Partition Labels in that it seeks all possible partitions via backtracking instead of a greedy single solution.
LeetCode 316: Remove Duplicate Letters – This problem isn’t about partitioning, but it uses the concept of last occurrence indices to make greedy decisions (ensuring each letter appears once in the result). It’s a good example of how knowing the last position of characters can guide a solution strategy in string problems.

763. Partition Labels - Detailed Explanation

Problem Statement

Hints

Brute Force Approach

Implementation (Python):

Implementation (Java):

Optimized Approach

Implementation (Python):

Implementation (Java):

Edge Cases and Common Mistakes

Alternative Variations

Related Problems