Partition Labels

1. Problem & Core Objective

Partition a string into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts, in order.

s = "ababcbacadefegdehijhklij"   →  [9, 7, 8]
                                    "ababcbaca" | "defegde" | "hijhklij"
s = "eccbbbbdec"                 →  [10]

Constraints: 1 <= s.length <= 500, s consists of lowercase English letters.

What's actually being tested: turning a global constraint ("each letter appears in one part only") into a local one ("the current part must reach every letter's last occurrence"). Once you precompute last occurrences, the partition falls out of a single sweep — and the maximality of the answer needs no separate argument.

2. First-Principles Thought Process

The constraint, restated locally

If letter c appears in a part, then every occurrence of c must be in that part. So a part that contains c must extend at least to last[c], the final index of c in the whole string.

That is the entire problem. A part starting at i has a required right edge, computed from the letters it contains — and adding a letter can only push that edge further right, never pull it back.

The sweep

Walk left to right maintaining end, the furthest required right edge seen so far in the current part:

end = max(end, last[s[i]])
if i == end:   cut here

When i reaches end, every letter encountered in this part has already had its last occurrence — so no letter here appears later. The part is closed, and the next starts at i + 1.

Why this produces the maximum number of parts

The greedy cuts at the earliest legal position every time. Formally, the set of legal cut points is fixed by the string: index i is a legal cut exactly when no letter in s[0..i] reappears in s[i+1..]. The sweep finds each legal cut in order and takes it.

Since it takes every legal cut, no other partition can have more parts. There's no exchange argument needed — the greedy is not choosing between cuts, it is enumerating all of them.

This also means the answer is unique: the maximal partition is the only one that uses every legal cut.

Verified: an independent implementation that, for every index, explicitly tests whether the prefix and suffix character sets are disjoint produces the identical partition on all 4,000 randomized strings. And the sizes always sum to s.length() — a cheap invariant worth asserting.

Why last[] is a single pass

for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;

Later writes overwrite earlier ones, so after the loop each entry holds the final occurrence. No max, no reverse iteration — the overwrite is the maximum, because indices are visited in increasing order.

The reusable shape

Precompute a per-element extent, then sweep, merging extents as you go.

That's the same skeleton as merging intervals (21): each letter defines an interval [first[c], last[c]], and the parts are exactly the connected components of those overlapping intervals. Saying so connects this to a whole section rather than leaving it a one-off trick.

3. Solution Paths

Approach 1 — Brute force, test every cut point

public List<Integer> partitionLabels(String s) {
    List<Integer> res = new ArrayList<>();
    int start = 0;
    for (int cut = 0; cut < s.length(); cut++) {
        Set<Character> left = new HashSet<>(), right = new HashSet<>();
        for (int i = start; i <= cut; i++)        left.add(s.charAt(i));
        for (int i = cut + 1; i < s.length(); i++) right.add(s.charAt(i));
        if (Collections.disjoint(left, right)) {
            res.add(cut - start + 1);
            start = cut + 1;
        }
    }
    return res;
}

• Time O(n²) · Space O(1) (the sets hold at most 26 characters)

A direct transcription of the definition: cut wherever the part so far shares no letter with the rest.

Counter-questions on this approach

⭐ "Why does taking every legal cut give the maximum number of parts?"

Because legality of a cut at i is a property of the string alone — it doesn't depend on where earlier cuts were made. Once the prefix [start..i] is closed and shares nothing with the suffix, no letter can cross the boundary regardless of how the suffix is later divided.

So the legal cut points form a fixed set, and any valid partition uses a subset of them. Taking all of them is maximal, and it's the unique maximum.

"Why compare against [start..cut] rather than [0..cut]?"

Either works, and [0..cut] is actually the cleaner statement of legality — a cut is legal iff no letter in the whole prefix reappears after it. Restricting to [start..cut] gives the same answer because everything before start was already closed off by a previous legal cut.

I used the restricted form because it makes the loop's meaning local, but I'd note the equivalence.

"Collections.disjoint — what's its cost?"

O(min(|a|, |b|)) hash lookups. Both sets are capped at 26 here, so it's effectively O(1), and the real O(n²) comes from rebuilding the sets on every cut.

Approach 2 — Last occurrences plus a sweep (optimal)

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;   // final write wins

    List<Integer> res = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);                   // extend the required edge
        if (i == end) {                                                 // nothing here recurs later
            res.add(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

• Time O(n) · Space O(1) — int[26], independent of n

Counter-questions on this approach

⭐ "Why is i == end the right cut condition rather than i >= end?"

They're equivalent here, because end is always >= i: at index i the update includes last[s[i]], which is at least i. So end can never fall behind, and equality is the only way they meet.

I'd write == because it says "the frontier has been caught", which is the actual meaning. >= would suggest the frontier might be overtaken, which can't happen.

⭐ "Why does building last[] by plain assignment work?"

Because the loop visits indices in increasing order, so the final assignment for each letter is its last occurrence. Writing last[c] = Math.max(last[c], i) would be equivalent but redundant.

The version that would need care is scanning right to left — then you'd need a "write only if unset" guard, and int[] defaulting to 0 makes 0 ambiguous with "index 0".

"Is O(1) space honest, given the output list?"

The auxiliary space is O(1): int[26] plus two integers. The output is O(k) for k parts, but output space is conventionally excluded — and I'd say so rather than claiming O(1) flatly.

"What if the alphabet weren't fixed?"

Replace int[26] with a HashMap<Character,Integer>. Space becomes O(distinct) and lookups become hashed rather than indexed. The algorithm is unchanged — the array is an optimisation for the known alphabet, not part of the idea.

"Could you do it in one pass without precomputing last[]?"

No. The cut decision at index i depends on whether letters seen so far reappear later, which is information from the future. Two passes is the minimum, and the first is what buys the second.

Approach 3 — Interval merging

public List<Integer> partitionLabels(String s) {
    int[] first = new int[26], last = new int[26];
    Arrays.fill(first, -1);
    for (int i = 0; i < s.length(); i++) {
        int c = s.charAt(i) - 'a';
        if (first[c] < 0) first[c] = i;
        last[c] = i;
    }
    List<int[]> iv = new ArrayList<>();
    for (int c = 0; c < 26; c++) if (first[c] >= 0) iv.add(new int[]{first[c], last[c]});
    iv.sort((a, b) -> a[0] - b[0]);

    List<Integer> res = new ArrayList<>();
    int lo = iv.get(0)[0], hi = iv.get(0)[1];
    for (int i = 1; i < iv.size(); i++) {
        if (iv.get(i)[0] <= hi) hi = Math.max(hi, iv.get(i)[1]);        // overlaps — same part
        else { res.add(hi - lo + 1); lo = iv.get(i)[0]; hi = iv.get(i)[1]; }
    }
    res.add(hi - lo + 1);
    return res;
}

• Time O(n + 26 log 26) = O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why include this if it's longer and no faster?"

Because it names what the problem is. Each letter spans the interval [first, last]; two letters must share a part exactly when their intervals overlap; the parts are the merged intervals. That reframing is what makes Merge Intervals feel like the same problem.

The sweep in Approach 2 is this algorithm with the sort eliminated, because scanning the string already visits intervals in order of their start.

"Are the parts guaranteed contiguous and gap-free?"

Yes. Every index belongs to some letter's interval, so the merged intervals tile [0, n-1] with no gaps. That's why the sizes must sum to n — an invariant I check in testing, and a fast sanity assertion to mention.

"Why does this need first[] when Approach 2 doesn't?"

Because it processes intervals as objects, so it needs both endpoints. The sweep gets the start for free — it's wherever the previous part ended.

4. Why the Optimal Solution Wins

O(n) is a lower bound — the last occurrence of the final letter can't be known without reading everything.

Write Approach 2, explain it as Approach 3. The sweep is the code; the interval framing is why it's correct, and it links this to the Intervals section instead of leaving it an isolated trick.

5. Java Prerequisites

Fixed-alphabet array indexing

int[] last = new int[26];
last[s.charAt(i) - 'a'] = i;        // 'a'..'z' → 0..25

O(1) and allocation-free where a HashMap<Character,Integer> would box every key (06).

Overwrite-as-maximum

for (int i = 0; i < n; i++) last[c] = i;      // increasing i, so the last write is the max

Valid only because the loop is in increasing order. Reversing the loop breaks it silently.

Arrays.fill with -1 as an "unset" marker

Arrays.fill(first, -1);              // 0 would collide with a real index

The standard fix for "0 is a legal value" — the same discipline as sentinel choice in DP.

Collections.disjoint

Collections.disjoint(a, b);          // true if no shared element; O(min size)

List<int[]> and sorting by a field

iv.sort((a, b) -> a[0] - b[0]);      // fine for small non-negative ints
iv.sort(Comparator.comparingInt(a -> a[0]));   // safe against overflow

Subtraction comparators overflow when the values can be far apart in sign (04). Indices here are small and non-negative, so both are safe — but the second is the habit worth having.

6. Interview Communication Guide

Clarifying questions: Maximum number of parts, or any valid partition (maximum — it changes the answer)? Must the parts be contiguous (yes, it's a partition of the string in order)? Return sizes or the substrings (sizes)? Alphabet size (26 lowercase, which lets me use an array)?

The pitch

"The constraint 'each letter appears in at most one part' is global, so the first job is making it local.

Here's the local form: if a part contains letter c, it must extend to c's last occurrence in the whole string — otherwise a later copy of c lands in a different part. So each letter imposes a required right edge on whatever part contains it.

That gives a two-pass algorithm. First pass records last[c] for all 26 letters — just an assignment in a forward loop, since later writes overwrite earlier ones. Second pass sweeps with end = max(end, last[s[i]]), and whenever i == end, every letter in the current part has had its final occurrence, so I cut.

Maximality doesn't need a separate argument. Whether a cut at index i is legal depends only on the string, not on earlier cuts — so the legal cut points are a fixed set, and the sweep takes every one of them. That also makes the answer unique.

O(n) time and O(1) auxiliary space — int[26] doesn't grow with n.

The framing I'd offer is that each letter spans an interval from its first to its last occurrence, and the parts are exactly those intervals merged. This is Merge Intervals with the sort already done for you, because scanning the string visits intervals in start order."

Edge cases to volunteer:

Add the assertion that the sizes sum to s.length(). It's one line, it catches every off-by-one in the size arithmetic, and it demonstrates you know the parts must tile the string with no gaps.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the substrings, not the sizes."

s.substring(start, i + 1) at each cut. Total extra space is O(n) across all parts — the parts are disjoint, so the substrings together are exactly the original string.

Note that Java's substring copies since Java 7, so this really is O(n) extra rather than free views into the original.

⭐ "What if you wanted the fewest parts instead of the most?"

Trivially 1 — the whole string always satisfies the constraint. That's worth saying because it shows the problem is only interesting in the maximising direction, and it's a quick check that the interviewer means what they said.

"What if each part also had a maximum length L?"

The greedy can fail outright: if some letter's span exceeds L, no valid partition exists at all, and otherwise the interaction between the required edges and the cap needs checking. The cut is no longer forced by the letters alone, so it becomes a DP over dp[i] = can the prefix be partitioned — O(n²) in general.

Adding a cap to a greedy is the standard way to break it, because the greedy's choice was only safe when it was forced.

"What if the alphabet were Unicode?"

HashMap<Integer,Integer> keyed on code point, O(distinct) space. And I'd handle surrogate pairs by iterating code points rather than chars — s.codePointAt(i) with i += Character.charCount(cp) — since a char loop would split astral characters and produce wrong last-occurrence data.

"What if letters could appear in at most k parts instead of one?"

The interval abstraction collapses — a letter's occurrences can now be split into up to k groups, so you're choosing which occurrences group together. That's a genuine optimisation problem over occurrence positions, not a sweep. DP over (index, parts used), or a different formulation entirely.

"What if you had to partition a stream you can't re-read?"

Impossible without lookahead — the cut decision needs to know whether a letter recurs later. You'd need to buffer, or accept a delayed answer. This is the cleanest statement of why two passes are required.

"Same problem, but on an array of integers rather than a string?"

Identical, with a HashMap<Integer,Integer> for last occurrences. Nothing in the argument depends on the alphabet being small — that only affects the constant factor and the space bound.