Partition Labels
Module 22 · Greedy
Problem
Given a string s, partition it into as many parts as possible so that
each letter appears in at most one part — every occurrence of a
given letter must fall entirely within a single partition. Return the
list of partition lengths. (LeetCode 763.)
Examples
Example 1
s = "ababcbacadefegdehijhklij"Output[9,7,8]Explanation. ababcbaca","defegde","hijhklij
Example 2
s = "eccbbbbdec"Output[10]Constraints
1 ≤ s.length ≤ 500, lowercase English letters only.
Attempt it first
The constraint — every occurrence of a letter must be in one partition
— means a partition can't end at some position i if any letter seen
so far in the current partition still has a LATER occurrence beyond
i. Before opening anything, think about how you'd know, at every
position while scanning left to right, whether it's safe to end the
current partition right there — what single piece of information about
each letter would let you answer that in O(1) per character?