629. Tile Sequences
A word game has tiles with an uppercase letter printed on each one; the string tiles lists them, and the same letter may appear on several tiles. A player lines up one or more of the tiles in a row and reads the letters from left to right. Two rows count as the same sequence if they spell the same letters, even when different physical tiles were used.
Return how many different non-empty sequences of letters can be formed. Generating every sequence and counting them is too slow for the biggest inputs; count by length and by letter instead.
Example 1
- Input:
- tiles = "XXY"
- Output:
- 8
- Explanation:
The sequences are
X,Y,XX,XY,YX,XXY,XYX,YXX: eight in total.
Example 2
- Input:
- tiles = "MMMM"
- Output:
- 4
- Explanation:
Only the lengths 1, 2, 3 and 4 give different sequences:
M,MM,MMM,MMMM.
Example 3
- Input:
- tiles = "Z"
- Output:
- 1
- Explanation:
A single tile makes one sequence,
Z.
Constraints
- 1 ≤
tiles.length≤ 12 tilesconsists only of uppercase English letters.
The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(26 * n^2)
- Space
- O(n^2)