Partition Labels

Q: What is the time complexity of Partition Labels?

O(n) : one pass records each letter's last position and a second pass places the cuts. The table of last positions has 26 entries for any length of string, so the extra space is O(1) , not counting the output.

MediumGreedy Hashing

+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 cdc, and no part can be cut again.

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, and the best answer cuts at every such place. Rescanning the string for each place is quadratic. Record each letter's last position first, and one left to right pass finds every cut: a part must stretch to the last copy of every letter inside it.

Test every gap

Correct, but does not finish on the largest tests

Intuition

A cut in one of the n-1 gaps is allowed when no letter appears on both sides of it. Making every allowed cut gives the most parts: between two neighbouring allowed cuts, every letter has all its copies inside, so the piece is a valid part, and no valid answer can cut anywhere else.

So test each gap: collect the letters on each side 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, so you cut. Each test reads the whole string, about n² reads in total: 2.5 × 10^9 for n = 5 × 10^4.

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

Treat each letter as an interval from its first position to its last. A part that holds a letter must cover its whole interval, so overlapping intervals share a part, and the overlap spreads: if a overlaps b and b overlaps c, all three are in one part. Merge the overlapping intervals; each merged block is a part.

Merging needs the intervals in order of start, and you get that without sorting: walk the string and take a letter's interval at its first position. In codingisfun, i is [3, 6] and n is [4, 10], and g, s, f and u all start before 10, so they merge into [3, 10]. With at most 26 letters, the position tables 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

You do not need the first positions. Read left to right and keep end, the farthest last position of any letter in the current part. Each letter you read stretches end to its own last copy if that is farther.

When i reaches end, every letter of the part has its last copy at or before i, so the gap after i is allowed. Before that, some letter you read still has a copy to the right, so no earlier gap in the part is allowed. The pass cuts at exactly the allowed gaps. In abacdcefe, a sets end to 2 and the part closes at i = 2; c sets it to 5 and the next part closes at 5.

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

Cutting at 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 a cut there splits the a's and the b's.
Off by one in the length: a part from start to end, both included, has end-start+1 letters.
Returning cut positions instead of lengths. For abacdcefe the answer is [3, 3, 3], not [2, 5, 8].
Forgetting the last part in the gap version. No gap follows it, so add n-start after the loop.

Frequently asked questions3

What is the time complexity of Partition Labels?

O(n): one pass records each letter's last position and a second pass places the cuts. The table of last positions has 26 entries for any length of string, so the extra space is O(1), not counting the output.

Is Partition Labels a merge intervals problem?

Yes. Each letter covers the interval from its first copy to its last, and merging the overlapping intervals gives the parts. The greedy pass is the same merge done on the fly, with end as the right edge of the merged block so far.

How many parts can Partition Labels return?

Between 1 and 26. Each part owns at least one letter that appears nowhere else, and there are only 26 lowercase letters. A string with every letter once gives 26 parts of length 1; a string that starts and ends with the same letter gives one part.

def partitionLabels(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "abacdcefe"

Expected Output

[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 questions3

Similar problems