Partition Labels

The problem

Cut the string s into parts so that no letter appears in more than one part, and make as many parts as you can. A part is a stretch of neighboring letters, and the parts together cover s from its first letter to its last. Return the lengths of the parts as a list, in the order the parts appear in s.

What to write

function solve(s: string): number[]

Input
s = "ababcbacadefegdehijhklij"

Output
[9,7,8]

Input
s = "eccbbbbdec"

Output
[10]

Constraints

s contains lowercase English letters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The string holds only lowercase letters, so there are at most 26 different letters to keep track of, however long the string is. The parts are stretches of neighboring letters in their original order, so the only thing to decide is where to cut.

2. Hint 2: Ask a smaller question

   Take "abac". The first part must contain the first letter, a. How far does that force the first part to go? Does the b inside it change anything? Now try "abacb".

3. Hint 3: Name the pattern

   A part must reach the last copy of every letter in it. As soon as it does, you may cut, and cutting there is always safe, because one cut never blocks another. Taking each cut the moment it is allowed is a greedy choice. First record the last position of each letter. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   While you read a part, keep the farthest last position of any letter read so far in that part. The part cannot end before that position. When the position you are reading is that farthest position, no letter of the part appears later.

5. Hint 5: Sketch the pseudocode

   Record the last position of each letter. Set start and end to 0 and make an empty list. For each position i: end = the larger of end and the last position of the letter at i. If i equals end: add end - start + 1 to the list, then start = i + 1. Return the list.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Track the last occurrence of every character. A part ends when the scan reaches the furthest last occurrence required by its characters.

The slow way

Try every way to cut: between each pair of neighboring letters you either cut or you do not. Keep the ways in which no letter lands in two parts, and return the one with the most parts. This is correct, but the 24 letters of example 1 can be cut in more than 8 million ways.

The insight

Whether you may cut after a position does not depend on any other cut. You may cut there exactly when no letter up to that position appears again later. So nothing has to be weighed up: take every cut the moment it is allowed, which is a greedy choice. To spot such a place in one pass, know the last position of each letter.

Step by step

1. Record the last position of each letter. A part that holds a letter must hold every copy of it, so the part cannot end before the last copy. Positions count from 0, and a later copy overwrites the entry of an earlier one.
2. Keep the lengths, the start of the part and how far it must reach. The answer is a list of lengths. A length needs the position where the part began, and a cut needs the farthest position the part is known to need. Both begin at 0, the first letter.
3. The part must reach the last position of this letter as well. This letter is now inside the part, so its last copy must be inside too. If that copy lies beyond the farthest position so far, the part has to stretch to it. Otherwise nothing changes.
4. At the farthest position the part must reach, record its length. Every letter read in this part has its last copy at or before this position, so none of them appears later. Both ends count: positions 9 to 15 hold 15 - 9 + 1 = 7 letters.
5. The next part starts at the next letter. Nothing from the finished part comes back, so the rest of the string is the same task again, beginning one position further on.
6. Return the lengths in the order of the parts. The cuts were found from left to right, so the lengths are already in the order the parts appear in the string.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Record the last position of each letter
  const last = new Map();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);
  // 2. Keep the lengths, the start of the part and how far it must reach
  const out = [];
  let end = 0,
    start = 0;
  for (let i = 0; i < s.length; i++) {
    // 3. The part must reach the last position of this letter as well
    end = Math.max(end, last.get(s[i]));
    // 4. At the farthest position the part must reach, record its length
    if (i === end) {
      out.push(end - start + 1);
      // 5. The next part starts at the next letter
      start = i + 1;
    }
  }
  // 6. Return the lengths in the order of the parts
  return out;
}

function solve(s: string): number[] {
  // 1. Record the last position of each letter
  const last = new Map<string, number>();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);
  // 2. Keep the lengths, the start of the part and how far it must reach
  const out: number[] = [];
  let end = 0,
    start = 0;
  for (let i = 0; i < s.length; i++) {
    // 3. The part must reach the last position of this letter as well
    end = Math.max(end, last.get(s[i])!);
    // 4. At the farthest position the part must reach, record its length
    if (i === end) {
      out.push(end - start + 1);
      // 5. The next part starts at the next letter
      start = i + 1;
    }
  }
  // 6. Return the lengths in the order of the parts
  return out;
}

def solve(s):
    # 1. Record the last position of each letter
    last = {}
    for i, char in enumerate(s):
        last[char] = i
    # 2. Keep the lengths, the start of the part and how far it must reach
    out = []
    start = end = 0
    for i, char in enumerate(s):
        # 3. The part must reach the last position of this letter as well
        end = max(end, last[char])
        # 4. At the farthest position the part must reach, record its length
        if i == end:
            out.append(end - start + 1)
            # 5. The next part starts at the next letter
            start = i + 1
    # 6. Return the lengths in the order of the parts
    return out

Example 1, traced

Input
s = "ababcbacadefegdehijhklij"

Output
[9,7,8]

Why it works

A cut is allowed exactly when no letter before it appears after it, and that does not depend on the other cuts. Removing an allowed cut only joins two parts into one, so the most parts come from making every allowed cut. The scan position equals the farthest last position of the letters read so far exactly at those places, so the method cuts at each of them.

Time and space

Time O(n), extra space O(26 + output). Two passes read the n letters: one records last positions and one finds the cuts, with a fixed amount of work per letter, so the time is O(n). The record holds at most 26 letters, and the answer holds one length per part.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep the farther of the two positions. If each letter overwrites how far the part must reach, example 1 cuts after its sixth letter, where the last b is, although a and c appear again later.
• Move the start after every cut. If it stays at 0, example 1 returns [9, 16, 24]: each length is then measured from the beginning of the string.
• Count both ends of a part: its length is end minus start plus one. Without the plus one, example 1 returns [8, 6, 7], and a part of one letter gets length 0.

Pattern

Greedy choice. Builds on Two Sum and Jump Game.

Keep going