Skip to main content

1079. Letter Tile Possibilities

medium

Count the number of distinct non-empty sequences you can form using the printed letters on a set of tiles. Backtracking with frequency counts — the classic 'permutations with duplicates' pattern.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You have n tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

Constraints

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

Examples

Example 1

Input
tiles = "AAB"
Output
8

Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2

Input
tiles = "AAABBC"
Output
188

Example 3

Input
tiles = "V"
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count letter frequencies first. The order of repeated letters doesn't matter — only the frequency does.

Hint 2

Recurse: at each call, for each letter with count > 0, pick it (increment answer + 1), decrement count, recurse, restore count.

Hint 3

Every recursive entry past depth 0 represents a valid sequence — that's where the +1 comes from.

Hint 4

Time scales with the total number of distinct sequences, which can be bounded by sum over k of k!/repeats.

Solution approach

Reveal approach

Count letter frequencies into an int[26] counts array. Recursive count(): result = 0. For c in 0..25: if counts[c] > 0, result += 1 (the new sequence ending in letter c), counts[c]--, result += count(), counts[c]++ (restore). Return result. Total answer is count() called once on the original frequency map. The 'permutations with duplicates' insight: by iterating distinct letters and decrementing their count, we never count the same sequence twice — we always pick a representative copy from each group of identical letters. Time is bounded by the total distinct sequence count, which for tiles.length = 7 is at most a few hundred thousand. Space is O(26 + n) for counts plus recursion.

Complexity

Time
O(sum of permutations with duplicates)
Space
O(n)

Related patterns

  • backtracking
  • recursion
  • permutations-with-duplicates

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

More Recursion practice problems

See all Recursion problems →