How do you approach Letter Tile Possibilities?

Count the frequency of each letter.

What are common mistakes on Letter Tile Possibilities?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Letter Tile Possibilities

MediumAlgorithms

Description

You have n tiles, each printed with an uppercase letter (given as the string tiles). Return the number of distinct non-empty sequences of letters you can make using these tiles.

Example 1

Input: tiles = "AAB"

Output: 8

Explanation: A, B, AA, AB, BA, AAB, ABA, BAA.

Constraints

- 1 <= tiles.length <= 7 - tiles consists of uppercase English letters

Letter Tile Possibilities: approach, complexity and pitfalls

A medium backtracking problem, graded against 7 test cases (5 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

Count the frequency of each letter.
At each step, use any letter with remaining count, add one sequence, and recurse with that count reduced.

The optimal approach

Show the approach: The approach

Backtracking over letter counts. Tally letter frequencies. At each node, for every letter still available, that single choice forms one new sequence; decrement its count and recurse to extend it, then restore. Summing across all branches counts every distinct sequence.

Time: O(sequences). Space: O(unique letters).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.