Partition Labels

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Split a string of lowercase letters into as many pieces as possible so that every letter appears in at most one piece. Return the sizes of the pieces in order. Joining the pieces must give back the original string.

    It is a compact greedy question that is really an intervals question in disguise: each letter covers the span from its first to its last occurrence. Original problem: LeetCode 763.

    Example

    "abcadefgdhij" splits into "abca", "defgd", "h", "i", "j".
    "abcadefgdhij" splits into "abca", "defgd", "h", "i", "j".
    Input:  "abcadefgdhij"
    Output: [4, 5, 1, 1, 1]      # "abca" | "defgd" | "h" | "i" | "j"
    Input:  "zz"
    Output: [2]
    Input:  "xyz"
    Output: [1, 1, 1]

    Constraints (assumed)

    • 1 ≤ length ≤ 500.
    • Lowercase English letters only.

    What this question tests

    • Turning "each letter in one piece" into "each piece must reach its letters' last occurrences".
    • A greedy cut, and an argument for why cutting as early as possible gives the most pieces.
    • Seeing the link to merging intervals.

    Questions to ask first

    1. Return the sizes or the pieces themselves? (Here: sizes.)
    2. Only lowercase letters? Decides between a 26-slot array and a hash map.
    3. Must the pieces keep the original order? (Yes; we only cut, never reorder.)
    4. Empty string? Return an empty list.