Classic problem #1079MediumHash TableStringBacktrackingCounting
Letter Tile Possibilities
Real-world version: Rows That Can Be Laid From the TilesTracked in this browser only
Read Letter Tile Possibilities on LeetCode(opens in a new tab)
The statement here is our own: the same inputs, outputs and technique.
A bag holds tiles, each stamped with one uppercase letter, given by tiles. Tiles may be laid out in a row in any order, using anywhere from one of them up to all of them.
Return how many different non-empty strings can be laid out. Two rows count as the same string when they read alike.
Examples
Example 1
- Input
- tiles = "AB"
- Output
- 4
The rows are A, B, AB and BA.
Example 2
- Input
- tiles = "AA"
- Output
- 2
The two tiles read alike, so the only rows are A and AA.
Example 3
- Input
- tiles = "ABC"
- Output
- 15
Three rows of one tile, six of two tiles and six of all three.
Constraints
- 1 <= tiles.length <= 7
- tiles holds only uppercase English letters
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
Python
def num_tile_possibilities(tiles: str) -> int:Java
public int numTilePossibilities(String tiles)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's