Partition Labels

Medium

The problem

Cut the string s into as many pieces as possible so that no letter shows up in more than one piece. The pieces, joined back in order, must give s again. Return the length of each piece, in order.

Example 1
Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]
The pieces are "ababcbaca", "defegde" and "hijhklij". Every letter lives in only one piece.
Example 2
Input: s = "eccbbbbdec"
Output: [10]
The first letter e also appears at the very end, so the whole string must be one piece.

Limits

1 ≤ len(s) ≤ 100,000
s has only lowercase English letters

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A piece must contain every occurrence of each of its letters. How far must it extend?

The idea

Record the last index of each letter; scan, extending the current end to the max last index; when i reaches end, cut a piece.

Target: O(n) time

Go function shape

func partitionLabels(s string) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// PartitionLabels: split s so each letter appears in at most one part; return the part sizes.
// Greedy: a part must reach at least the last occurrence of every letter inside it.
func PartitionLabels(s string) []int {
	last := map[rune]int{}
	for i, r := range s {
		last[r] = i
	}
	var sizes []int
	start, end := 0, 0
	for i, r := range s {
		end = max(end, last[r]) // extend the part to cover this letter's last occurrence
		if i == end {           // nothing inside the part appears later: close it
			sizes = append(sizes, end-start+1)
			start = i + 1
		}
	}
	return sizes
}

Read the lesson: Greedy