Partition Labels

+10

You get a string s of lowercase letters. Cut it into as many consecutive parts as you can so that every letter appears in one part only: if a letter shows up in a part, all of its copies are in that part. Return the lengths of the parts from left to right.

Function

partitionLabels(s: string) → integer-array

sstring: the string to cut, lowercase letters only
Returnsinteger-array: the length of each part, from left to right

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s holds lowercase English letters only.
The parts keep their order and together make up all of s, so the lengths add up to s.length.

Examples

Input: s = "abacdcefe"
Output: [3, 3, 3]
Explanation: The a's sit at 0 and 2, the c's at 3 and 5 and the e's at 6 and 8, so the cuts fall after aba and after cdc. No part can be cut again, because each one starts and ends with the same letter.

+14 hidden tests on Submit

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A cut is allowed only where no letter appears on both sides of it, and the best answer cuts at every such place. Testing each place by rescanning the string is quadratic. Record the last position of each letter first, and one left to right pass finds every cut, because a part has to stretch until the last copy of every letter inside it.

Test every gap

Correct, but does not finish on the largest tests

Intuition

There are n-1 gaps between neighbouring letters. A cut in a gap is allowed only when no letter appears on both sides of it, since a letter split by the cut would sit in two parts. Making every allowed cut gives the most parts. Take a piece between two neighbouring allowed cuts: none of its letters appears to the left of the left cut or to the right of the right cut, so all their copies are inside the piece and it is a valid part. And any valid answer can only cut at allowed gaps, so no answer has more parts.

So test each gap: collect the letters on its left and on its right, and cut if the two sets share nothing. In abacdcefe the gap after aba has a and b on the left and c, d, e and f on the right. Nothing is shared, so you cut. The gap after ab has an a on both sides, so you do not.

Each test reads the whole string, and there are n-1 gaps, so the work is about n² letter reads. With 50,000 letters that is 2.5 × 10^9 reads, far too slow for the largest tests.

Algorithm

Set start = 0, where the current part begins.
For each gap cut from 1 to n-1 (the gap right before s[cut]), mark the letters of s[0..cut-1] and the letters of s[cut..n-1].
If no letter is marked on both sides, add cut-start to the answer and set start = cut.
After the loop, add the last part, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Merge each letter's span

Intuition

Think of each letter as an interval, from its first position to its last. A part that holds a letter must cover that whole interval. So two letters whose intervals overlap must share a part, and the overlap spreads: if a overlaps b and b overlaps c, all three end up in one part.

That is the merge intervals problem. Record each letter's first and last position in one pass. Then take the intervals in order of where they start and merge the ones that overlap. Each merged block is one part, and the gaps between blocks are exactly the allowed cuts. You get the intervals in order of start with no sorting: walk the string again and take a letter's interval when you stand on its first position.

In codingisfun the intervals in order are c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] and u [9, 9]. The first three stand alone. From i on, every interval starts at or before 10, where n ends, so they merge into [3, 10], a part of 8 letters.

The string has at most 26 different letters, so there are at most 26 intervals, and the tables of first and last positions have a fixed size.

Algorithm

In one pass over s, record first and last, the first and last position of each letter.
Walk s again. When position i is the first position of its letter, that letter's interval [i, last] is the next one in order of start.
If the interval starts after the current block's end, close the block, of length end-start+1, and start a new block at i.
Either way, set end = max(end, last).
Close the final block and return the lengths.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Grow each part to its last letter

Intuition

The first positions are not needed at all. Read the string from left to right and keep end, the farthest last position of any letter in the current part. When you read a letter at i, its last copy must be in this part too, so stretch end to last[s[i]] if that is farther.

When i reaches end, every letter you read in this part has its last copy at or before i. No letter crosses the gap after i, so a cut there is allowed. Close the part, of length end-start+1, and start the next one at i+1.

Why is cutting at the first chance the right greedy choice? Before i reaches end, some letter of the part still has a copy further right, so no earlier cut is allowed. And the pass never misses an allowed gap: if no letter crosses the gap after i, every letter of the part ends by i, so end equals i right there. The pass cuts at exactly the allowed gaps, which gives the most parts possible.

In abacdcefe the last positions are a 2, b 1, c 5, d 4, e 8 and f 7. Reading a sets end to 2, b leaves it there, and at i = 2 the part closes with length 3. The c sets end to 5 and the part closes at 5, again length 3. The e part closes at 8.

Algorithm

In one pass, store last[c], the last position of each letter c, in an array of 26.
Set start = 0 and end = 0.
For each position i, set end = max(end, last[s[i]]).
If i == end, add end-start+1 to the answer and set start = i+1.
Return the lengths.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Pitfalls and edge cases

The greedy pass is short, so the bugs hide in which position you compare against and in the part lengths.

Cutting when you reach the current letter's last copy instead of the part's end. In abcba the c at index 2 is its own last copy, but the a's run to index 4, so a cut there would split both a and b.
Off by one in the length. A part from start to end, both included, has end-start+1 letters.
Returning the cut positions instead of the lengths. For abacdcefe the answer is [3, 3, 3], not [2, 5, 8].
Forgetting the last part when you cut at gaps. The final part has no gap after it, so add n-start once the loop is over.
Expecting one part per distinct letter. zebraz has five different letters and a single part, because the z's hold everything between them together.

Frequently asked questions4

What is the time complexity of Partition Labels?

One pass records the last position of each letter and a second pass places the cuts, so the time is O(n). The table of last positions has 26 entries whatever the length of the string, so the extra space is O(1), not counting the output.

Why does the greedy approach work for Partition Labels?

The current part must reach the last copy of every letter it contains, so no cut before end is allowed. At end no letter of the part appears later, so the cut is allowed, and taking it never hurts the rest of the string. The pass therefore cuts at every allowed gap and at nothing else, which is the most parts any answer can have.

Is Partition Labels a merge intervals problem?

Yes, in disguise. Each letter covers the interval from its first copy to its last, overlapping intervals must share a part, and merging them gives exactly the parts. The greedy pass is the same merge done on the fly: end is the right edge of the merged block so far.

How many parts can Partition Labels return?

Between 1 and 26. No letter can appear in two parts, so each part owns at least one letter of its own, and there are only 26 lowercase letters. A string with every letter once gives 26 parts of length 1, and a string that starts and ends with the same letter gives a single part.

Python

def partitionLabels(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "abacdcefe"

Expected

[3, 3, 3]

Partition Labels

Function

Constraints

Examples

Hints

Solution

Test every gap

Merge each letter's span

Grow each part to its last letter

Pitfalls and edge cases

Frequently asked questions4

Similar problems