Solution: Letter Tile Possibilities

Statement

You are given a string, tiles, consisting of uppercase English letters. You can arrange the tiles into sequences of any length (from 1 to the length of tiles), and each sequence must include at most one tile, tiles[i], from tiles.

Your task is to return the number of possible non-empty unique sequences you can make using the letters represented on tiles[i].

Constraints:

• $1 \leq$ tiles.length $\leq 7$

• The tiles string consists of uppercase English letters.

Solution

This problem would have been straightforward if the tiles had no duplicates and we only needed to find sequences of the same length as the given tiles. In that case, we could simply calculate the total unique sequences using $n!$ (where $n$ is the length of the tiles).

However, in this problem, we need to find all unique sequences of any length—from 1 to the full length of the tiles—while accounting for duplicate tiles. To achieve this, we take the following approach:

We begin by sorting the letters in tiles so that similar letters are grouped. This allows us to systematically explore possible letter sets without repeating unnecessary work.

To generate sequences of lengths ranging from 1 to $n$, we consider each letter one by one. We start with a single character, determine its possible sequences, then move to two-character combinations, find their possible sequences, and so on. For each new character, we have two choices: either include the current letter in our selection or skip it and move to the next one. By exploring both choices, we generate all possible letter sets.

To prevent counting the same sequences multiple times due to duplicate letters, we ensure (in the previous step) that duplicate letter sets are not counted more than once while generating different letter sets. Then, for each set, we calculate how many distinct sequences can be formed by applying the updated formula for permutations, which accounts for repeated letters:

• $\frac{n!}{c!}$ ...