Partition Labels

1. The obvious way

   For each cut point check all letters on both sides: O(n x 26) per cut, O(n²).

2. The key insight

   Precompute the last position of every letter. Scan the string with the current part's end = farthest last-position seen so far. When the scan reaches that end, close the part (size = end - part start + 1) and begin a new one.

3. The algorithm
   1. Record the last index of each letter.
   2. Walk the string; end = max(end, last index of this letter).
   3. Position == end? Record the part size and start a new part.
   4. Return the sizes.

Watch it run

part end = 2

def partition_labels(s):
    last = {letter: position for position, letter in enumerate(s)}   # last position of each letter
    sizes = []
    part_start = 0
    part_end = 0
    for position, letter in enumerate(s):
        part_end = max(part_end, last[letter])         # the box must reach this letter's last book
        if position == part_end:
            sizes.append(part_end - part_start + 1)    # nobody inside has books outside: close the box
            part_start = position + 1
    return sizes

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.