DSA Factory
Free Greedy lessonsGreedy · Stage 2 · Reach and jump · Step 4

Split so letters stay together

Cut a string into as many pieces as possible so that each letter appears in only one piece, by extending each piece to the last occurrence of every letter inside it. About 18 minutes.

A piece must close over its letters

Cut a string into pieces so that no letter shows up in two pieces, and make as many pieces as possible. If a piece contains the letter a, it must stretch all the way to the last a in the string, or that a would land in another piece.

So first record, for every letter, the position of its last appearance. Then every piece has a minimum size set by the letters it already holds.

Last position: of each letter, found in a first pass.
A piece can only end: where all its letters are finished.

Extend, then close

Scan the string with an end marker. At each position, push the end marker to the larger of itself and the last position of the current letter. Every letter inside the piece may force it longer.

When the scan reaches the end marker, nothing inside the piece appears later, so close the piece there. Record its size and start a new piece at the next position.

Reached the end marker? close the piece.
Every letter: may push the end marker further.
In code
end = max(end, last[ch])
# the piece must reach this far
String a, b, a, b, c, b, a, c, d, e. Last positions: a at 6, b at 5, c at 7, d at 8, e at 9.
1
0
2
1
1
2
2
3
3
4
2
5
1
6
3
7
4
8
5
9
i

Letter a ends last at 6, so the piece stretches to at least 6.

Move 1 of 5
Quick check

The string is a b c. What are the piece sizes?

  1. A1, 1, 1
  2. B3
  3. C2, 1
Show the answer

1, 1, 1. Each letter appears once, so every letter can be its own piece.

Your problem

Split into the most pieces

Given a string s of lowercase letters, cut it into as many pieces as possible so that every letter appears in at most one piece. Return the sizes of the pieces in order.

Example
s = "ababcbacadefegdehijhklij" → [9, 7, 8]

1 ≤ s.length ≤ 100,000 · lowercase letters only

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve