The Partition Labels problem can be solved efficiently by tracking the last occurrence of each character and scanning with two pointers. By greedily expanding partitions to include the last appearance of every character seen so far, we ensure each letter is confined to a single segment. This method guarantees the maximal number of partitions while keeping time complexity linear and space proportional to unique letters.
Problem Statement
Given a string s, partition it into as many parts as possible so that no letter appears in more than one part. Each partition must be contiguous, and concatenating all partitions should reconstruct the original string. Return a list of integers representing the sizes of these partitions.
For example, the string "ababcbacadefegdehijhklij" can be split into ["ababcbaca", "defegde", "hijhklij"], ensuring every letter appears in only one partition. Invalid splits would either repeat letters across partitions or create partitions smaller than the greedy maximum possible.
Examples
Example 1
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
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]
Example details omitted.
Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
Solution Approach
Precompute last occurrences
Create a hash map storing the last index of each character. This allows the two-pointer scan to know how far each partition must extend to include all instances of its letters.
Two-pointer greedy scan
Use a start and end pointer. Iterate through the string, updating the end pointer to the maximum last occurrence of characters seen. When the current index reaches end, record the partition size and move start to the next index.
Collect partition sizes
Each time the end pointer is reached, compute the partition size as end - start + 1, append it to the result list, and advance the start pointer to continue scanning the remaining string. This ensures maximal partitions without overlap.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(k) |
Time complexity is O(n) since each character is scanned once. Space complexity is O(k) where k is the number of unique lowercase letters, used for the hash map storing last occurrences.
What Interviewers Usually Probe
- Check if the candidate tracks last indices efficiently using a hash map.
- Watch for correct handling of greedy expansion of partitions without missing characters.
- Notice if candidate avoids unnecessary repeated scans of the same characters.
Common Pitfalls or Variants
Common pitfalls
- Failing to update the end pointer correctly when a character's last occurrence is beyond current end.
- Splitting partitions too early, causing repeated letters in multiple segments.
- Assuming contiguous letters must be grouped by first appearance only, ignoring last occurrence.
Follow-up variants
- Partition a string where each letter can appear at most twice instead of once, adjusting partition expansion accordingly.
- Return the actual substring partitions instead of sizes, requiring careful slice management during two-pointer scan.
- Handle uppercase and lowercase letters distinctly while maintaining maximal partitioning logic.
How GhostInterview Helps
- Automatically computes last occurrences and tracks two-pointer partitions for instant feedback.
- Highlights incorrect early splits and suggests correct greedy expansion to maximize partitions.
- Provides step-by-step partition sizes and validates them against the problem constraints to prevent repeated letters.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What pattern does Partition Labels follow?
It follows a two-pointer scanning pattern with invariant tracking, expanding partitions to include the last occurrence of all letters seen.
Why is a hash map needed in Partition Labels?
The hash map stores last occurrences of characters, allowing the end pointer to expand correctly for maximal partitions.
Can Partition Labels be solved without a greedy approach?
A naive solution might repeatedly scan for repeated letters, but greedy two-pointer scanning ensures O(n) efficiency.
What are common mistakes when implementing Partition Labels?
Common errors include splitting too early, missing last occurrences, or not tracking end pointer updates.
How does GhostInterview optimize Partition Labels solving?
GhostInterview guides the candidate through last-index tracking, greedy partition expansion, and validation of partition sizes for correctness.
Need direct help with Partition Labels instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Partition Labels from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Reorganize a string so that no two adjacent characters are the same, if possible, using a greedy approach.
Open problem page#942 DI String MatchReconstruct a permutation from a DI string using two-pointer scanning, carefully tracking the increasing and decreasing invariants.
Open problem page#567 Permutation in StringCheck if a string contains a permutation of another string using two-pointer scanning and hash table techniques.
Open problem page