0726MediumHash TableStringGreedy

Cutting The Bead Spool Into Clean Pieces

Tracked in this browser only

Trains the technique from

LeetCode 2405Optimal Partition of String

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A bead spool is threaded with one bead per position, and beads records their colours left to right, one lowercase letter per colour.

The spool has to be snipped into pieces. Each piece is a run of beads that were next to each other on the spool, every bead belongs to exactly one piece, and no piece may carry two beads of the same colour.

Return the smallest number of pieces the spool can be cut into.

Examples

Example 1

Input: beads = "gnome"
Output: 1

No colour repeats anywhere on the spool, so the whole spool is already a clean piece.

Example 2

Input: beads = "cadbcbd"
Output: 2

Cutting after the fourth bead gives the pieces `cadb` and `cbd`, and neither piece carries a colour twice.

Example 3

Input: beads = "wwww"
Output: 4

Every bead is the same colour, so no piece can hold two of them and each bead ends up in a piece of its own.

Constraints

1 <= beads.length <= 10^5
beads holds lowercase English letters only.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_segments(beads: str) -> int:

Java

public int fewestSegments(String beads)

The intended approach

Time O(n) for a spool of n beads.Space O(1), since the colour set holds at most 26 entries.

Keep the set of colours already sitting in the piece currently being cut and read the spool once. While the next bead's colour is new to the piece it joins it; when the colour is already there the piece has to stop before that bead, so the count of pieces goes up and the set restarts holding just that bead. The set never exceeds the 26 colours, so the membership tests are constant work.

Pythonentry point: fewest_segments

def fewest_segments(beads):
    # Walk the spool keeping the colours already in the piece being cut.  A bead
    # whose colour is present ends that piece, and the new piece opens holding that
    # bead.  Every bead is looked at once and the colour set never holds more than
    # the 26 possible colours.
    # Time O(n).  Space O(1).
    pieces = 1
    seen = set()
    for colour in beads:
        if colour in seen:
            pieces += 1
            seen = {colour}
        else:
            seen.add(colour)
    return pieces

The obvious version

Fill a table over prefixes of the spool: the fewest pieces for the first `end` beads is one more than the best over every earlier cut point whose trailing run has no repeated colour. The trailing runs are extended backwards until a colour repeats.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_segments(beads):
    n = len(beads)
    best = [0] * (n + 1)
    for end in range(1, n + 1):
        best[end] = end
        used = set()
        start = end - 1
        while start >= 0:
            if beads[start] in used:
                break
            used.add(beads[start])
            if best[start] + 1 < best[end]:
                best[end] = best[start] + 1
            start -= 1
    return best[n]

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in