Coding Interview PatternsPartition Labels
MediumGreedy Techniques
Partition Labels
Explanation & Solution
Description
You are given a string s. You want to partition the string into as many parts as possible so that each letter appears in at most one part.
Return a list of integers representing the size of each part.
Note that the partition must cover the entire string, and the concatenation of all parts must equal the original string.
Input: s = "ababcbacadefegdehijhklij"
Output:[9,7,8]
0
9
1
7
2
8
Explanation: The partition is "ababcbaca", "defegde", "hijhklij". Each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is valid but produces fewer parts.
Constraints
1 <= s.length <= 500sconsists of lowercase English letters
Approach
Greedy Techniques pattern
1. Record Last Occurrences
- Iterate through the entire string and build a map where each character points to its last index in the string
- For example, in
"ababcbacadefegdehijhklij", the last occurrence of'a'is index8,'b'is index5, etc.
2. Initialize Partition Tracking
- Maintain two pointers:
start(beginning of the current partition) andend(the farthest index the current partition must reach) - Both start at
0
3. Greedily Expand the Partition
- For each character at index
i, updateendto be the maximum ofendand the character's last occurrence - This ensures the current partition extends far enough to include all occurrences of every character seen so far
4. Close the Partition
- When
i === end, the current index has reached the farthest point needed by any character in this partition - Record the partition size as
end - start + 1 - Move
starttoi + 1to begin the next partition
5. Return All Partition Sizes
- After one full pass through the string, the
resultarray contains the size of each partition
Key Insight
- The greedy approach works because once you know the last occurrence of each character, you can determine the minimum extent of each partition in a single scan
- Time complexity is O(n) with two passes through the string
- Space complexity is O(1) since the character map holds at most 26 lowercase English letters
Visualization
Input:
[a, b, a, b, c, b, a, c, a, d, e, f, e, g, d, e, h, i, j, h, k, l, i, j]
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
28 steps