Partition Labels

MEDIUM✓ CHIP-TIMEDLC #763 — FULL STATEMENT ↗

The drill: Cut a string into the maximum number of contiguous pieces so that no letter spills across a cut — every occurrence of a letter must stay inside a single piece. Report each piece's length in order.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string of letters needs to be sliced into contiguous pieces, reading left to right, so that no single letter has occurrences spread across two different pieces — every appearance of a letter must live inside one piece.

The goal is finding the maximum number of pieces the string can be split into under that rule, in the order the pieces appear, and reporting how long each piece is.

Pieces are read off in order and cover the whole string with no character skipped or reused — the lengths reported should sum back to the string's total length.

EX 01

s = "abac"

→ [3, 1]

A'S LAST OCCURRENCE PULLS B INTO THE FIRST PIECE

EX 02

s = "abcabc"

→ [6]

EVERY LETTER REPEATS AT THE FAR END — ONE PIECE

EX 03

s = "aaaa"

→ [4]

SINGLE REPEATED LETTER, ONE PIECE

the string uses lowercase letters only
every occurrence of a letter must stay confined to a single piece
pieces are reported in left-to-right order, covering the whole string
piece lengths always sum to the total length of the input string

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A cut can only happen where nothing forces the piece open further. What would tell you a piece can't possibly end yet?

HINT 2 THE STRUCTURE

Track, for the current open piece, the farthest-right position any letter inside it is still going to reappear. The piece can't close before that position.

HINT 3 ONE STEP FROM THE ANSWER

Precompute each letter's last index in one pass. Walk the string extending the current piece's boundary to the max last-index seen so far; the moment your walk reaches that boundary, cut.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE LAST-INDEX WALKPATTERN · GREEDY — LAST-INDEX MAPs = "abac"

LAST INDEX OF EACH LETTER

a → 2

b → 1

c → 3

STEP 1

Precompute each letter's last index: a→2, b→1, c→3. Now walk left to right, stretching the current piece to the farthest last-index seen.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/partition-labels.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}
        result = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                result.append(end - start + 1)
                start = i + 1
        return result

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        result = []
        start = 0
        while start < len(s):
            end = start
            i = start
            while i <= end:
                last = s.rfind(s[i])  # rescans the whole string every time
                end = max(end, last)
                i += 1
            result.append(end - start + 1)
            start = end + 1
        return result

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public int[] partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> parts = 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) {
                parts.add(end - start + 1);
                start = i + 1;
            }
        }
        int[] result = new int[parts.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = parts.get(i);
        }
        return result;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 22 LN

class Solution {
    public int[] partitionLabels(String s) {
        List<Integer> parts = new ArrayList<>();
        int n = s.length();
        int start = 0;
        while (start < n) {
            int end = start;
            int i = start;
            while (i <= end) {
                int last = s.lastIndexOf(s.charAt(i));
                end = Math.max(end, last);
                i++;
            }
            parts.add(end - start + 1);
            start = end + 1;
        }
        int[] result = new int[parts.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = parts.get(i);
        }
        return result;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 23 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED