Show problems as
Classic problem #2405MediumHash TableStringGreedy

Optimal Partition of String

Real-world version: Cutting The Bead Spool Into Clean Pieces
Tracked in this browser only
Read Optimal Partition of String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_segments(beads: str) -> int:
Java
public int fewestSegments(String beads)

More on the same topics