219. Partition Labels

Why this mechanism works

Any character encountered in the current part forces that part to extend through the character's final occurrence. Keep the farthest of these obligations. When the scan reaches that boundary, every character seen in the part is complete, so closing immediately is safe and maximizes opportunities for later parts.

State and boundaries

end is the farthest last occurrence among characters in the current part. start is that part's first index.

Protocol

1. Record each character's last index.
2. Scan the string.
3. Extend end with the current character's last index.
4. At i==end append i-start+1.
5. Begin a fresh part at i+1.

Visualization

ababcbaca | defegde | hijhklij
first part's obligations extend through index 8
lengths 9,7,8

Python implementation

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=0; char='a'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=1; char='b'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=2; char='a'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=3; char='b'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=4; char='c'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=5; char='b'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=6; char='a'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='ababcbacadefegdehijhklij'; i=7; char='c'

... 50 intermediate state changes omitted ...

L4 partition_labels: for i, char in enumerate(text):
text='ababcbacadefegdehijhklij'; last={'a':8, 'b':5, 'c':7, 'd':14, 'e':15, ...}; output=[9, 7]; start=16; end=23; i=22; char='i'

L4 partition_labels: for i, char in enumerate(text):
text='ababcbacadefegdehijhklij'; last={'a':8, 'b':5, 'c':7, 'd':14, 'e':15, ...}; output=[9, 7]; start=16; end=23; i=23; char='j'

L7 partition_labels: output.append(i - start + 1)
text='ababcbacadefegdehijhklij'; last={'a':8, 'b':5, 'c':7, 'd':14, 'e':15, ...}; output=[9, 7, 8]; start=16; end=23; i=23; char='j'

L8 partition_labels: start = i + 1
text='ababcbacadefegdehijhklij'; last={'a':8, 'b':5, 'c':7, 'd':14, 'e':15, ...}; output=[9, 7, 8]; start=24; end=23; i=23; char='j'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='abc'; i=0; char='a'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='abc'; i=1; char='b'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='abc'; i=2; char='c'

L2 partition_labels: last = {char: i for i, char in enumerate(text)}
text='abc'; last={'a':0, 'b':1, 'c':2}

L3 partition_labels: output, start, end = [], 0, 0
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[]; start=0; end=0

L4 partition_labels: for i, char in enumerate(text):
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[]; start=0; end=0; i=0; char='a'

L7 partition_labels: output.append(i - start + 1)
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[1]; start=0; end=0; i=0; char='a'

L8 partition_labels: start = i + 1
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[1]; start=1; end=0; i=0; char='a'

... 4 intermediate state changes omitted ...

L4 partition_labels: for i, char in enumerate(text):
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[1, 1]; start=2; end=1; i=2; char='c'

L5 partition_labels: end = max(end, last[char])
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[1, 1]; start=2; end=2; i=2; char='c'

L7 partition_labels: output.append(i - start + 1)
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[1, 1, 1]; start=2; end=2; i=2; char='c'

L8 partition_labels: start = i + 1
text='abc'; last={'a':0, 'b':1, 'c':2}; output=[1, 1, 1]; start=3; end=2; i=2; char='c'

Why the solution is correct

No legal cut can occur before end because it would split some character's occurrences. At end, every character in the part has its final occurrence inside it, so the cut is valid. Taking every earliest legal cut cannot reduce later choices and yields the maximum number of parts.

Time and space

Expected O(n) time and O(u) auxiliary map space for u distinct characters, plus O(n) worst-case output lengths.

Common mistakes

Using the first occurrence instead of the last closes parts too early. Returning endpoints instead of lengths changes the requested output.

Reasoning card

Transfer exercise

Return the substrings themselves and account for the total copying cost.