Show problems as
Classic problem #3144MediumHash TableStringDynamic ProgrammingCounting

Minimum Substring Partition of Equal Character Frequency

Real-world version: Fewest Even Tile Cartons
Tracked in this browser only
Read Minimum Substring Partition of Equal Character Frequency on LeetCode(opens in a new tab)

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

Tiles come off a kiln one at a time. Each tile's glaze colour is recorded as a lowercase letter, and the letters are written down in arrival order, giving the string tiles.

The packing line fills cartons from that stream. Every tile goes into exactly one carton, and each carton takes a block of tiles that arrived consecutively, so the cartons cut tiles into consecutive pieces with nothing left over.

A carton is even when all the colours inside it appear the same number of times as one another. A carton holding a single colour is even, whatever the count.

Return the smallest number of cartons the line can use so that every carton is even.

Examples

Example 1

Input
tiles = "aabab"
Output
2

Fill the first carton with the single tile `a` and the second with `abab`, which holds two `a` tiles and two `b` tiles. Both cartons are even, so two cartons are enough.

Example 2

Input
tiles = "abaccc"
Output
3

The cartons `ab`, `a` and `ccc` are each even: the first holds one tile of each of its two colours, and the other two hold a single colour apiece.

Example 3

Input
tiles = "aabbcc"
Output
1

Each of the three colours arrives twice, so one carton holding the whole stream is already even.

Constraints

  • 1 <= tiles.length <= 1000
  • Every character of tiles is a lowercase English letter.

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_even_cartons(tiles: str) -> int:
Java
public int fewestEvenCartons(String tiles)

More on the same topics