763. Partition Labels (Medium)

Problem

Given a string s, partition it into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts.

Example

s = "ababcbacadefegdehijhklij" → [9, 7, 8]
s = "eccbbbbdec" → [10]

LeetCode 763 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try all partition points

For each candidate split, verify that every character on the left never appears on the right. Quadratic.

def partition_labels(s):
    if not s:
        return []
    n = len(s)
    # Find the smallest k such that s[:k] and s[k:] share no character
    for k in range(1, n + 1):
        if not (set(s[:k]) & set(s[k:])):                  # L1: O(n) per k
            return [k] + partition_labels(s[k:])           # L2: recurse on the rest
    return [n]

function partitionLabels(s: string): number[] {
    if (!s) return [];
    const n = s.length;
    for (let k = 1; k <= n; k++) {
        const left = new Set(s.slice(0, k));               // L1: O(n) per k
        const right = new Set(s.slice(k));
        let overlap = false;
        for (const ch of left) { if (right.has(ch)) { overlap = true; break; } }
        if (!overlap) return [k, ...partitionLabels(s.slice(k))];  // L2: recurse
    }
    return [n];
}

func partitionLabels(s string) []int {
    if s == "" { return nil }
    n := len(s)
    var result []int
    for k := 1; k <= n; k++ {
        left := map[byte]bool{}
        for i := 0; i < k; i++ { left[s[i]] = true }      // L1: O(n) per k
        overlap := false
        for i := k; i < n; i++ {
            if left[s[i]] { overlap = true; break }
        }
        if !overlap {
            result = append(result, k)
            rest := partitionLabels(s[k:])                  // L2: recurse on the rest
            result = append(result, rest...)
            return result
        }
    }
    return []int{n}
}

final class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        let characters = Array(s)
        func valid(_ start: Int, _ end: Int) -> Bool {
            let inside = Set(characters[start...end])
            for index in characters.indices where (index < start || index > end) && inside.contains(characters[index]) { return false }
            return true
        }
        func split(_ start: Int) -> [Int]? {
            if start == characters.count { return [] }
            for end in start..<characters.count where valid(start, end) {
                if let rest = split(end + 1) { return [end - start + 1] + rest }
            }
            return nil
        }
        return split(0) ?? []
    }
}

Building both sets is $O(n)$ per candidate cut, and we try up to n cuts → $O(n²)$ total.

Complexity

Time: $O(n²)$ .
Space: $O(n)$ .

Approach 2: Precompute last-seen index + greedy extension (canonical)

Precompute last[ch], the final index of each character. Walk the string; maintain a running end = the max last[ch] seen so far. When the walking index reaches end, the current window is the smallest valid partition ending at end.

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}    # L1: O(n), last occurrence of each char
    result = []                                 # L2: O(1)
    start = end = 0                             # L3: O(1)
    for i, ch in enumerate(s):                  # L4: single pass, n iterations
        end = max(end, last[ch])                # L5: O(1), extend window if needed
        if i == end:                            # L6: O(1), window is closed
            result.append(i - start + 1)        # L7: O(1) amortized
            start = i + 1                       # L8: O(1)
    return result

function partitionLabels(s: string): number[] {
    const last = new Map<string, number>();
    for (let i = 0; i < s.length; i++) last.set(s[i], i);  // L1: O(n)
    const result: number[] = [];                            // L2: O(1)
    let start = 0;                                         // L3: O(1)
    let end = 0;
    for (let i = 0; i < s.length; i++) {                   // L4: single pass, n iterations
        end = Math.max(end, last.get(s[i])!);              // L5: O(1), extend window if needed
        if (i === end) {                                    // L6: O(1), window is closed
            result.push(i - start + 1);                    // L7: O(1) amortized
            start = i + 1;                                 // L8: O(1)
        }
    }
    return result;
}

func partitionLabels(s string) []int {
    last := make(map[byte]int)
    for i := 0; i < len(s); i++ { last[s[i]] = i }         // L1: O(n)
    var result []int                                        // L2: O(1)
    start, end := 0, 0                                     // L3: O(1)
    for i := 0; i < len(s); i++ {                          // L4: single pass, n iterations
        if last[s[i]] > end { end = last[s[i]] }           // L5: O(1), extend window if needed
        if i == end {                                       // L6: O(1), window is closed
            result = append(result, i-start+1)             // L7: O(1) amortized
            start = i + 1                                  // L8: O(1)
        }
    }
    return result
}

final class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        let characters = Array(s)
        var last: [Character: Int] = [:]
        for (index, character) in characters.enumerated() { last[character] = index }
        var result: [Int] = [], start = 0, end = 0
        for (index, character) in characters.enumerated() {
            end = max(end, last[character]!)
            if index == end { result.append(end - start + 1); start = index + 1 }
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (build last map)	$O(1)$	n	$O(n)$
L4-L8 (greedy scan)	$O(1)$	n	$O(n)$ ← dominates
L5 (extend end)	$O(1)$	n	$O(n)$
L6-L8 (emit partition)	$O(1)$ amortized	at most n	$O(n)$

Two $O(n)$ passes: one to build last, one to scan and emit partitions.

Complexity

Time: $O(n)$ , driven by L4/L5/L6-L8 (two linear passes).
Space: $O(26)$ = $O(1)$ for ASCII alphabets.

Why greedy works

The moment the walking index equals end, every character in [start, end] is fully contained in the window (no later occurrence anywhere past end). So [start, end] is valid, and it’s the smallest such window, any earlier cut would miss a later occurrence of some character.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Union-Find / interval-merge formulation (conceptually equivalent)

Each character’s first and last occurrence form an interval. Merge overlapping intervals; the merged sizes are the answer. Same $O(n)$ via the same last-index trick, included as a conceptual map to problem 56 (Merge Intervals).

def partition_labels(s):
    first, last = {}, {}
    for i, ch in enumerate(s):
        first.setdefault(ch, i)
        last[ch] = i
    intervals = sorted((first[ch], last[ch]) for ch in first)        # L1: O(k log k), k ≤ 26
    merged = []
    for a, b in intervals:                                            # L2: linear sweep
        if merged and a <= merged[-1][1]:
            merged[-1] = (merged[-1][0], max(merged[-1][1], b))
        else:
            merged.append((a, b))
    return [b - a + 1 for a, b in merged]

function partitionLabels(s: string): number[] {
    const first = new Map<string, number>();
    const last = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
        if (!first.has(s[i])) first.set(s[i], i);
        last.set(s[i], i);
    }
    const intervals: [number, number][] = [];
    for (const ch of first.keys()) {
        intervals.push([first.get(ch)!, last.get(ch)!]);
    }
    intervals.sort((a, b) => a[0] - b[0]);                           // L1: O(k log k), k ≤ 26
    const merged: [number, number][] = [];
    for (const [a, b] of intervals) {                                 // L2: linear sweep
        if (merged.length > 0 && a <= merged[merged.length - 1][1]) {
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], b);
        } else {
            merged.push([a, b]);
        }
    }
    return merged.map(([a, b]) => b - a + 1);
}

import "sort"

func partitionLabels(s string) []int {
    first := make(map[byte]int)
    last := make(map[byte]int)
    for i := 0; i < len(s); i++ {
        if _, ok := first[s[i]]; !ok { first[s[i]] = i }
        last[s[i]] = i
    }
    type iv struct{ a, b int }
    var intervals []iv
    for ch := range first { intervals = append(intervals, iv{first[ch], last[ch]}) }
    sort.Slice(intervals, func(i, j int) bool { return intervals[i].a < intervals[j].a }) // L1
    var merged []iv
    for _, x := range intervals {                                     // L2: linear sweep
        if len(merged) > 0 && x.a <= merged[len(merged)-1].b {
            if x.b > merged[len(merged)-1].b { merged[len(merged)-1].b = x.b }
        } else {
            merged = append(merged, x)
        }
    }
    result := make([]int, len(merged))
    for i, x := range merged { result[i] = x.b - x.a + 1 }
    return result
}

final class Solution {
    func partitionLabels(_ s: String) -> [Int] {
        let characters = Array(s)
        var bounds: [Character: (Int, Int)] = [:]
        for (index, character) in characters.enumerated() {
            bounds[character] = (bounds[character]?.0 ?? index, index)
        }
        let intervals = bounds.values.sorted { $0.0 < $1.0 }
        var merged: [(Int, Int)] = []
        for interval in intervals {
            if let last = merged.last, interval.0 <= last.1 { merged[merged.count - 1].1 = max(last.1, interval.1) }
            else { merged.append(interval) }
        }
        return merged.map { $0.1 - $0.0 + 1 }
    }
}

Same answer, derived as the canonical “sort + sweep” merge-intervals template applied to per-character ranges. With a fixed alphabet (e.g., 26 letters), the sort is constant.

Complexity

Time: $O(n)$ given the bounded alphabet.
Space: $O(1)$ extra (alphabet-sized).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Try all splits	$O(n²)$	$O(1)$
Last-seen + greedy extension	$O(n)$	$O(1)$

Pattern: “first index encountering a character starts its interval; max(last[ch]) grows the window.”

Test cases

func partitionLabels(s string) []int {
    last := make(map[byte]int)
    for i := 0; i < len(s); i++ { last[s[i]] = i }
    var result []int
    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        if last[s[i]] > end { end = last[s[i]] }
        if i == end { result = append(result, i-start+1); start = i + 1 }
    }
    return result
}

# Quick smoke tests, paste into a REPL or save as test_763.py and run.
# Uses the canonical implementation (Approach 2: last-seen + greedy extension).

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    result = []
    start = end = 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            result.append(i - start + 1)
            start = i + 1
    return result

def _run_tests():
    assert partition_labels("ababcbacadefegdehijhklij") == [9, 7, 8]
    assert partition_labels("eccbbbbdec") == [10]
    assert partition_labels("a") == [1]              # single character
    assert partition_labels("abcd") == [1, 1, 1, 1]  # all unique, each its own partition
    assert partition_labels("aabb") == [2, 2]         # two non-overlapping pairs
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function partitionLabels(s: string): number[] {
    const last = new Map<string, number>();
    for (let i = 0; i < s.length; i++) last.set(s[i], i);
    const result: number[] = [];
    let start = 0;
    let end = 0;
    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, last.get(s[i])!);
        if (i === end) {
            result.push(i - start + 1);
            start = i + 1;
        }
    }
    return result;
}

const eq = (a: number[], b: number[]) => a.length === b.length && a.every((v, i) => v === b[i]);
console.assert(eq(partitionLabels('ababcbacadefegdehijhklij'), [9, 7, 8]));
console.assert(eq(partitionLabels('eccbbbbdec'), [10]));
console.assert(eq(partitionLabels('a'), [1]));              // single character
console.assert(eq(partitionLabels('abcd'), [1, 1, 1, 1]));  // all unique
console.assert(eq(partitionLabels('aabb'), [2, 2]));         // two non-overlapping pairs
console.log("all tests pass");

Strings, input
Hash Tables, last[ch] lookup

Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.
Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.

763. Partition Labels (Medium)

Problem

Try it yourself

Approach 1: Brute force, try all partition points

Approach 2: Precompute last-seen index + greedy extension (canonical)

Why greedy works

Approach 3: Union-Find / interval-merge formulation (conceptually equivalent)

Summary

Test cases

Related data structures

Related concepts