Partition Labels - Solution & Explanation
Problem Statement
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.
Return a list of integers representing the size of these parts.
Example 1:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
Example 2:
Input: s = "eccbbbbdec" Output: [10]
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
Approach Overview
Problem Overview: Given a string s, split it into as many parts as possible so that each letter appears in at most one partition. After splitting, concatenating all parts must still produce the original string. The goal is to return the size of each partition.
Approach 1: Greedy with Last Occurrence (O(n) time, O(1) space)
This is the optimal approach and relies on a simple greedy observation: a partition cannot end until you pass the last occurrence of every character currently inside it. First iterate through the string and store the last index where each character appears using a small lookup array or hash table. Then scan the string again while tracking the farthest last index among characters seen so far. When the current index matches that boundary, you can safely close the partition because all characters inside it will not appear later. This technique works well because the alphabet size is fixed (26 lowercase letters), giving O(1) space and O(n) total time.
Approach 2: Two-Pass Trick (O(n) time, O(1) space)
Another way to reason about the problem is to track how many times each character still appears ahead in the string. In the first pass, count frequencies of all characters. In the second pass, iterate through the string while decrementing the remaining count for each character. Maintain a set or counter of "active" characters currently present in the partition. When the remaining frequency of a character drops to zero, it means that character will not appear later. Once all active characters reach zero remaining occurrences, the current segment becomes a valid partition. This approach also runs in linear time and relies heavily on string traversal and counting logic.
Recommended for interviews: Interviewers typically expect the greedy last-occurrence method. It demonstrates the ability to recognize interval boundaries and apply a greedy strategy. Implementing the first pass to record last indices and the second pass to expand the partition boundary is straightforward and clearly shows optimal O(n) reasoning. The two-pass frequency trick is also valid but slightly less common in interview discussions.
Approach 1: Greedy Method with Last Occurrence
This approach uses a greedy method where we determine the possible endpoints of each partition by finding the last occurrence of each character. As we iterate through the string, we expand the end of the current partition to the maximum last occurrence index of all characters seen so far. The current partition ends once the current index matches this endpoint.
This C solution utilizes an array to store the last occurrence index of each character. As we iterate through the string, we calculate the endpoint of the current partition by checking the maximum last occurrence index of the characters seen so far. Once the end of the partition is reached, we record its size and move to the next partition.
Complexity
Time Complexity: O(n), where n is the length of the string, because we iterate over the string a constant number of times.
Space Complexity: O(1), as the space used for storing last occurrences is constant, not dependent on input size.
Approach 2: Two-Pass Trick
Another approach involves performing two passes over the string. The first pass is used to collect the rightmost occurrence of each character, and in the second pass, we calculate the sizes of partitions while maintaining the maximum index of characters on the go.
This C implementation performs a two-step traversal of the given string. Firstly, we map each character's last occurrence to create the partition scopes. In the walk-through, the size of a partition is determined when the maximum index matches the loop index, marking partition boundaries.
Complexity
Time Complexity: O(n) for length n of the string, taking linear scans for mapping and partitioning.
Space Complexity: O(1) since the space needed does not grow in relation to input size.
Approach 3: Greedy
We first use an array or hash table last to record the last occurrence of each letter in the string s.
Next, we use a greedy approach to partition the string into as many segments as possible.
Traverse the string s from left to right, while maintaining the start index j and end index i of the current segment, both initially set to 0.
For each letter c visited, get the last occurrence position last[c]. Since the end index of the current segment must not be less than last[c], let mx = max(mx, last[c]).
When visiting the index mx, it means the current segment ends. The index range of the current segment is [j,.. i], and the length is i - j + 1. We add this length to the result array. Then set j = i + 1 and continue to find the next segment.
Repeat the above process until the string traversal is complete to get the lengths of all segments.
Time complexity is O(n), and space complexity is O(|\Sigma|). Where n is the length of the string s, and |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Method with Last Occurrence | Time Complexity: O(n), where n is the length of the string, because we iterate over the string a constant number of times. |
| Two-Pass Trick | Time Complexity: O(n) for length n of the string, taking linear scans for mapping and partitioning. |
| Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Last Occurrence | O(n) | O(1) | Best general solution. Easy to reason about interval boundaries and commonly expected in interviews. |
| Two-Pass Frequency Trick | O(n) | O(1) | Useful when reasoning about remaining character counts rather than last indices. |
Video Solution
Partition Labels - Leetcode 763 - Python • NeetCode • 67,066 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Partition Labels easy or hard?
Partition Labels Python/Java solution
How to solve Partition Labels in O(n)?
What is the best approach for Partition Labels?
Is Partition Labels asked at Google/Amazon/Meta?
What data structure is used in Partition Labels?
What is the time complexity of Partition Labels?
Ready to solve this problem?
Practice Partition Labels with our built-in code editor and test cases.
Practice on FleetCode