763. Partition Labels

At a Glance

• Topic: greedy
• Pattern: Greedy (scan + last occurrence map)
• Difficulty: Medium
• Companies: Google, Amazon, Apple, Microsoft, Adobe
• Frequency: High
• LeetCode: 763

Problem (one-liner)

Partition string s into as many maximal parts as possible so that each character appears in only one part. Return part lengths in order. Input: s. Output: array of positive lengths.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “As many chunks as possible” with per-character exclusivity
• Precompute lastIndex[letter]
• Extend current chunk end to max(lastIndex[char]) for seen characters in this chunk; cut when index reaches end

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute — try cuts — exponential.
• Greedy — one pass with last-occurrence map — O(n) time / O(1) space (alphabet size). <- pick this in interview.

Optimal Solution

Go

package main

func partitionLabels(s string) []int {
	lastIndex := [26]int{}
	for index := range s {
		letter := s[index] - 'a'
		lastIndex[letter] = index
	}
	sizes := make([]int, 0, 8)
	chunkStart := 0
	chunkEnd := 0
	for index := range s {
		letter := s[index] - 'a'
		if lastIndex[letter] > chunkEnd {
			chunkEnd = lastIndex[letter]
		}
		if index == chunkEnd {
			sizes = append(sizes, chunkEnd-chunkStart+1)
			chunkStart = index + 1
		}
	}
	return sizes
}

JavaScript

function partitionLabels(s) {
	const lastIndex = new Map();
	for (let index = 0; index < s.length; index++) {
		lastIndex.set(s[index], index);
	}
	const sizes = [];
	let chunkStart = 0;
	let chunkEnd = 0;
	for (let index = 0; index < s.length; index++) {
		const letter = s[index];
		chunkEnd = Math.max(chunkEnd, lastIndex.get(letter));
		if (index === chunkEnd) {
			sizes.push(chunkEnd - chunkStart + 1);
			chunkStart = index + 1;
		}
	}
	return sizes;
}

Walkthrough

s = "ababcbacadefegdehbarhk"

Compute last indices; sweep extending chunk until index catches planned chunkEnd.

Invariant: when cursor reaches chunkEnd, every letter seen since last cut finishes before or at chunkEnd.

Edge Cases

• Single distinct letter repeated → [length]
• Already-separated letters → many chunks

Pitfalls

• Off-by-one chunk length
• Using first occurrence instead of last

Similar Problems

• 056. Merge Intervals — merge overlapping intervals framing.
• 435. Non-overlapping Intervals — greedy endpoint reasoning.
• 1899. Merge Triplets to Form Target — another greedy “cut when safe” story.

Variants

• Minimum partitions under exclusivity → same greedy yields maximal count.

Mind-Map Tags

#greedy #last-occurrence #string-partition #medium