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.

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

Diagram

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

Loading diagram…

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;
}