#763 Partition Labels
the problem
In plain words
Split string s into as many pieces as possible so each letter appears in at most one piece. Return the piece sizes in order.
in s = "ababcbacadefegdehijhklij"
out [9,7,8]
"ababcbaca", "defegde", "hijhklij".
in s = "eccbbbbdec"
out [10]
- 1 ≤ s.length ≤ 500
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy furthest reachInterval merging (sort by start)
Each letter is an interval [first, last]. The pieces are the merged intervals. You only need each letter's last index to know how far the current piece must stretch.
solutions
From brute force to optimal
Start a piece, then keep stretching its end to the last occurrence of every letter inside it.
- end = lastIndexOf(s[start]).
- For each i in the piece, end = max(end, lastIndexOf(s[i])).
- Record the size; the next piece starts at end + 1.
Every lastIndexOf scans the string.
Besides the output.
class Solution { public List<Integer> partitionLabels(String s) { List<Integer> sizes = new ArrayList<>(); int start = 0; while (start < s.length()) { int end = s.lastIndexOf(s.charAt(start)); // O(n) scan for (int i = start; i <= end; i++) { // every char inside drags the end end = Math.max(end, s.lastIndexOf(s.charAt(i))); } sizes.add(end - start + 1); start = end + 1; } return sizes; }}Precompute last[c]. Sweep i, stretching end = max(end, last[s[i]]). When i == end, cut.
- Fill last[26].
- end = max(end, last[s[i]]).
- If i == end: record end − start + 1, start = i + 1.
Two passes over the string.
A fixed array of 26 ints.
class Solution { public List<Integer> partitionLabels(String s) { int[] last = new int[26]; for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i; // last index of each letter List<Integer> sizes = new ArrayList<>(); int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, last[s.charAt(i) - 'a']); // this letter must stay inside if (i == end) { // nothing in the piece appears later sizes.add(end - start + 1); // cut here start = i + 1; } } return sizes; }}Dry run
in the room
How to say it in the interview
talk track
- Mention the intervals view (each letter is [first, last]; merge them). Then show the shortcut with only
last[].
traps
- Cutting as soon as a letter doesn't repeat. Letters seen earlier in the piece may still reappear later.
what they ask next
Follow-ups
Why is cutting at the first possible point optimal?
Cutting as early as allowed never blocks a later cut, so the greedy cut count stays ahead of any other valid split.
before you submit
Edge cases to test
- One letter → [1].
- All different letters, "abc" → [1, 1, 1].
- The first letter reappears at the very end, "abca" → one piece [4].
practise next
Similar problems
- #56Merge IntervalsMediumin Intervals
- #45Jump Game IIMediumin Greedy