Command Palette

Search for a command to run...

Hectal
Problem 33.6 · Greedy AlgorithmsMedium

Partition Labels

PatternGreedy ChoiceMerge Intervals

What it teaches: Extend the current part to the last occurrence of every letter inside it.

Practise it on judges as “Partition Labels”.

The problem

Split s into as many parts as possible so each letter appears in at most one part. Return the part sizes.

Example 1

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]

Constraints

  • 1 ≤ n ≤ 500

Pattern clues in the wording

  • → Each letter's span must stay in one part

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String s) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
s = "ababcbacadefegdehijhklij"
[9,7,8]
2
s = "eccbbbbdec"
[10]

From slow to fast

Approaches

1. Last occurrence sweep · O(n)
1

Last occurrence sweep

Time O(n) Space O(26)

end = max(end, last[s[i]]); when i == end, close the part.

Approach 1
import java.util.*;

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;
        List<Integer> out = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) { out.add(end - start + 1); start = i + 1; }
        }
        return out;
    }
}

Verdict: Merging letter spans like intervals, in one pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • One letter repeated (one part)
  • All distinct (n parts of 1)

Mistakes people make

  • Closing a part at the first letter's last occurrence without extending.

Interview

Follow-up questions

How is it an interval problem?