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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Letter Tile Possibilities and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →