Watch 10 video solutions for Partition Labels, a medium level problem involving Hash Table, Two Pointers, String. This walkthrough by NeetCode has 63,908 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 500s consists of lowercase English letters.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 | 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. |