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.

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!}$, where $c$ is the count of each repeated letter.

The more repeated letters in a set, the fewer unique ways it can be arranged.

We repeat this process for every possible letter set. Eventually, we sum the count of all these possible sequences to obtain the total number of unique non-empty sequences. Finally, we subtract one from our final count to exclude the empty set, as it does not contribute to valid arrangements.

Let’s look at the following illustration to understand this better.

Now, let’s look at the algorithm steps of this solution:

• Initialize a set, unique_letter_sets, to track unique letter sets.

• Sort the input string, tiles, to group identical letters together.

• Generate unique letter sets and count their permutations:

  • The function generate_sequences is used to recursively generate all possible letter subsets.

  • We calculate the number of valid sequences using count_permutations for each unique letter set. The count_permutations uses the helper function factorial(n), which computes the factorial of a given number.

• The recursive function, generate_sequences(tiles, current_letter_set, index, unique_letter_sets), works as follows:

  • ...