DSA Partition Labels

The problem

Partition Labels cuts a string into the most parts so that each letter appears in only one part. A cut after a position is legal only when every letter in the part has its last occurrence inside that part.

The answer in this article is the list of part sizes, with the parts themselves shown beside it. More parts is better, and each part is as short as its letters allow.

for s in ['ababcbacadefegdehijhklij', 'eccbbbbdec', 'abac', 'aaaa', 'abcd']:
    print('text:', s, 'length:', len(s))

The first case splits into three parts. The second case stays whole, because its letters reach across the whole string. The short cases pin down the edge behaviour at the end of the article.

Intuition: cut after each distinct letter ends

The first idea cuts as soon as the current letter will not appear again. It watches one letter at a time. It forgets that another letter in the same part may reach much further.

That forgetfulness is the trap. In the string abac, the letter b ends at index 1. The letter a in the same stretch ends at index 2, so a cut at index 1 would split a across two parts.

s = 'abac'
last = {}
for index, ch in enumerate(s):
    last[ch] = index
print('last of b:', last['b'])
print('last of a:', last['a'])
print('cut at index 1 legal:', last['a'] <= 1)

The cut must wait for the farthest last occurrence among all letters in the part. That single running value is the whole optimal method. The next sections build up to it.

Brute force: try every set of cuts

The brute force tries every combination of cut positions. A combination is valid when no letter appears in two parts. The valid combination with the most parts wins.

import itertools
def brute(s):
    n = len(s)
    tested = [0]
    best = None
    positions = list(range(n - 1))
    for r in range(len(positions), -1, -1):
        for cuts in itertools.combinations(positions, r):
            tested[0] += 1
            bounds = [-1] + list(cuts) + [n - 1]
            parts = [s[bounds[i] + 1:bounds[i + 1] + 1] for i in range(len(bounds) - 1)]
            seen = set()
            ok = True
            for part in parts:
                letters = set(part)
                if seen & letters:
                    ok = False
                seen |= letters
            if ok:
                return parts, tested[0]
    return best, tested[0]
parts, tested = brute('abac')
print('parts:', parts)
print('sizes:', [len(p) for p in parts])
print('cut sets tested:', tested)

A four-letter string already offers 8 cut sets. Each added letter doubles that count. The optimal scan answers in one pass, with no cut set ever built.

The optimal solution: cut when the scan reaches the farthest last

The farthest last is the largest last occurrence seen so far in the current part, and the part ends exactly when the scan index reaches that value. That one sentence is the whole method.

A first pass records the last occurrence of each letter. A second pass grows the farthest value and cuts on contact. Each part is as short as its letters allow, so the parts are as many as possible.

def partition_sizes(s):
    last = {}
    for index, ch in enumerate(s):
        last[ch] = index
    sizes = []
    parts = []
    start = 0
    farthest = 0
    for index, ch in enumerate(s):
        farthest = max(farthest, last[ch])
        if index == farthest:
            sizes.append(index - start + 1)
            parts.append(s[start:index + 1])
            start = index + 1
    return sizes, parts
for s in ['ababcbacadefegdehijhklij', 'eccbbbbdec', 'abac', 'aaaa', 'abcd']:
    sizes, parts = partition_sizes(s)
    print('text:', s)
    print('parts:', parts)
    print('sizes:', sizes)

Every case from the start of the article is answered. The long string gives sizes 9, 7, and 8. The string of one repeated letter gives a single part, however long it is.

Walkthrough: scanning abacabad

The walk shows the farthest value at each index. The state is one number. A cut happens exactly in the rows where the index equals that number.

s = 'abacabad'
last = {}
for index, ch in enumerate(s):
    last[ch] = index
farthest = 0
for index, ch in enumerate(s):
    farthest = max(farthest, last[ch])
    print(index, ch, 'must reach', farthest, 'cut here:', index == farthest)

The first cut lands at index 6, not at index 2 where a first short part might seem to end. The letter a reaches to index 6, and every cut before that point would split it. The answer is read off the two True rows.

Complexity

The scan makes two passes over the string, so its time is O(n) for a string of length n. Its space is one entry per distinct letter in the last table, plus the output list.

for n in [4, 10, 24]:
    print('length', n, '- scan steps:', 2 * n, ' brute cut sets:', 2 ** (n - 1))

At length 24 the scan takes 48 steps. The brute force would test over eight million cut sets. One running maximum replaces all of them.

Edge cases and pitfalls

Cutting when the current letter ends, instead of when the farthest last is reached, is the classic mistake. It splits any letter that reaches past the cut. The intuition section showed that failure on abac.

An empty string gives no parts. A string of distinct letters gives one part per letter. A string of one repeated letter gives one part, because that letter reaches to the final index from the very first position.

def partition_sizes(s):
    last = {}
    for index, ch in enumerate(s):
        last[ch] = index
    sizes = []
    start = 0
    farthest = 0
    for index, ch in enumerate(s):
        farthest = max(farthest, last[ch])
        if index == farthest:
            sizes.append(index - start + 1)
            start = index + 1
    return sizes
print('empty:', partition_sizes(''))
print('single letter:', partition_sizes('x'))
print('all same:', partition_sizes('aaaa'))
print('all distinct:', partition_sizes('abcd'))
print('abac:', partition_sizes('abac'))

Each short answer follows from the farthest rule alone. No case needs its own branch in the code. The empty string simply never enters the loop.