Cut a string into the most chunks so no letter crosses a cut

Greedy choices and intervals Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
text = "abacdc"
last = {ch: i for i, ch in enumerate(text)}
print(last, [last[ch] for ch in text])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A {'a': 2, 'b': 1, 'c': 5, 'd': 4} [2, 1, 2, 5, 4, 5]

Right: a later index overwrites an earlier one, leaving each letter's last position.

With these last positions, the piece starting at 'a' must run to index 2, and the next must run to index 5: lengths [3, 3].

Why not the others?
  • B {'a': 0, 'b': 1, 'c': 3, 'd': 4} [0, 1, 0, 3, 4, 3]. Those are first positions; the dict keeps the last assignment.
  • C {'a': 2, 'b': 1, 'c': 5, 'd': 4} [2, 1, 2, 3, 4, 5]. Each list entry looks up the letter's last index, so both c's give 5.

30-second answer

Record the last index of every letter. Scan left to right, stretching the current piece's end to the last index of each letter you see. When the scan reaches that end, no letter in the piece appears later, so cut there. O(n) time and O(alphabet) memory.

Practise saying it · 45 s. No recording, just a timer

Explain cutting into the most chunks.

Say your answer out loud, then check which of these points you covered:

  • Last index per letter
  • Stretch the piece end
  • Cut when reached

Deep dive

It is interval merging in disguise: each letter spans first-to-last index.

Cutting as soon as possible is what maximises the number of pieces.

A dict of last positions is built in one pass.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def chunk_sizes(text: str) -> list[int]:
    last = {ch: i for i, ch in enumerate(text)}  # final positions
    sizes: list[int] = []
    begin = end = 0
    for i, ch in enumerate(text):
        end = max(end, last[ch])
        if i == end:  # nothing in this piece appears later
            sizes.append(i - begin + 1)
            begin = i + 1
    return sizes

Common mistakes

  • Cutting when a letter's count reaches zero without tracking the furthest last index.
  • Returning the pieces instead of the lengths, or the reverse.

Senior take & follow-ups

Mention the interval view; it connects this to a pattern you already explained.

Follow-up questions

Think of your answer first, then open the hint.

  1. How is this like merging intervals?

    Show hint

    Each letter is an interval from its first to last index; the pieces are the merged blocks.

  2. What if you need the fewest pieces instead?

    Show hint

    One piece, the whole string, always works.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.