Letter Tile Possibilities

Count all distinct non-empty sequences you can form with a handful of letter tiles.

backtracking counting strings permutations

You are given a string `tiles` where each character represents a tile with a printed letter. You may choose any non-empty subset of tiles (1 to len(tiles) tiles) and arrange them in any order to form a sequence. Each tile can be used at most once, and tiles with the same letter are considered indistinguishable. Implement the function `def numTilePossibilities(tiles: str) -> int:` that returns the total number of distinct non-empty sequences that can be formed.

For example, with tiles = "AAB", you can form: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA" — 8 distinct sequences. Note that "AB" and "BA" are different even though they use the same tiles.

Constraints

1 <= len(tiles) <= 7
`tiles` consists of uppercase English letters (A-Z).
The number of distinct sequences fits in a 32-bit integer.
Time complexity should be O(n!) or O(2^n * n) where n = len(tiles).

Example

>>> numTilePossibilities("AAB")
8
>>> numTilePossibilities("AAABBC")
188
>>> numTilePossibilities("V")
1

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the problem as counting all distinct permutations of every non-empty subset of the available tiles.

You can use a character frequency array (26 ints) to avoid duplicates: at each step, try placing a letter that still has remaining count.

The answer is the sum over all lengths from 1 to n of the number of distinct permutations of length that length, which can be computed recursively by exploring frequency choices.

A simple recursive formula: if you have frequencies f, the total count is sum over each distinct letter with f[i] > 0 of (1 + results after decrementing f[i]).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.