Count how many non-empty sequences can be formed from a multiset of letter tiles.
Problem
You are given a string of uppercase English letters representing letter tiles. Each tile may be used at most once.
A sequence is any non-empty string that can be formed by choosing some of the tiles and arranging them in any order. Different positions in the original string represent different tiles, even if the letters are the same.
Return the number of distinct non-empty sequences that can be formed.
Notes
- Two sequences are considered the same if they have the same letters in the same order.
- You may use any subset of the tiles, including all of them or just one tile.
- Because the input may contain repeated letters, duplicate sequences should be counted only once.
Input Format
- A single string
tilesconsisting of uppercase English letters. - Each character represents one tile.
Output Format
- Return a single integer: the number of distinct non-empty sequences that can be formed from the tiles.
Constraints
tilescontains only uppercase English letters.- Duplicate letters may appear multiple times.
Example 1
Input
tiles = "AAB"
Output
8
Explanation
Distinct sequences are: A, B, AA, AB, BA, AAB, ABA, BAA.
Example 2
Input
tiles = "AAABBC"
Output
188
Explanation
There are many valid sequences of lengths 1 through 6. The total number of distinct non-empty sequences is 188.
Show 1 more example
Example 3
Input
tiles = "V"
Output
1
Explanation
Only one non-empty sequence can be formed: V.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.