Letter Tile Sequences

EasyBacktracking

Problem

You hold a rack of letter tiles given as a string tiles (letters may repeat). A sequence is any non-empty row of tiles taken from the rack, each tile used at most once.

Return how many distinct letter sequences you can form. Sequences of different lengths all count.

Example 1

Input:
tiles = "AAB"
Output:
8

"A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2

Input:
tiles = "V"
Output:
1

Constraints

  • 1 ≤ tiles.length ≤ 7
  • tiles contains only uppercase English letters.

Hint

Show the first hint

Two tiles with the same letter are interchangeable. Can you think in letters rather than tiles?

Walkthrough

How to approach it

01Clarify before coding

  • Does the empty sequence count? No, only non-empty ones.
  • Are 'AB' and 'BA' different? Yes, order matters.
  • Are the two A tiles in 'AAB' distinguishable? No: 'A' formed from either tile is the same sequence.

02Brute force

Generate all permutations of every length by position and put them in a set of strings.

Cost: Up to about e · n! position sequences (13,699 for 7 tiles), each built as a string; with repeated letters many are identical, so a set of strings is needed to deduplicate, costing O(n · e · n!) time and memory.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.