0796MediumHash TableStringDynamic ProgrammingCounting

Fewest Even Tile Cartons

Tracked in this browser only

Trains the technique from

LeetCode 3144Minimum Substring Partition of Equal Character Frequency

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.

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 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_even_cartons(tiles: str) -> int:

Java

public int fewestEvenCartons(String tiles)

The intended approach

Time O(26n + n^2) for n tiles, which is O(n^2): every start point of every prefix is visited once and the evenness test is constant time.Space O(n) for the table, plus the fixed 26 colour counts.

Let best[i] be the fewest cartons that can hold the first i tiles. For each i, widen the final carton leftwards one tile at a time, keeping a 26-slot colour count, the number of distinct colours in it and the largest of those counts. The carton is even exactly when the largest count multiplied by the number of distinct colours equals its width, and each even carton offers best[j] + 1 as a candidate for best[i].

Pythonentry point: fewest_even_cartons

def fewest_even_cartons(tiles):
    n = len(tiles)
    unreachable = n + 5
    best = [0] + [unreachable] * n
    for i in range(1, n + 1):
        counts = [0] * 26
        distinct = 0
        top = 0
        # widen the last carton leftwards, keeping its colour counts up to date
        for j in range(i - 1, -1, -1):
            c = ord(tiles[j]) - 97
            if counts[c] == 0:
                distinct += 1
            counts[c] += 1
            if counts[c] > top:
                top = counts[c]
            if top * distinct == i - j and best[j] + 1 < best[i]:
                best[i] = best[j] + 1
    return best[n]

The obvious version

Treat the cut positions as nodes and search breadth-first from position zero: from a position, every end position whose piece tallies out even is one carton further. The first time the end of the stream is reached, the number of layers walked is the answer. Each piece is tallied from scratch with a dictionary.

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_even_cartons(tiles):
    n = len(tiles)
    reached = [False] * (n + 1)
    reached[0] = True
    frontier = [0]
    cartons = 0
    while frontier:
        cartons += 1
        nxt = []
        for pos in frontier:
            for end in range(pos + 1, n + 1):
                if reached[end]:
                    continue
                tally = {}
                for ch in tiles[pos:end]:
                    tally[ch] = tally.get(ch, 0) + 1
                if len(set(tally.values())) == 1:
                    if end == n:
                        return cartons
                    reached[end] = True
                    nxt.append(end)
        frontier = nxt
    return n

How this problem was checked

Reference solution executed against 13 test cases — 13 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