Letter Tile Possibilities — Solution in Python, Java & C++
Letter Tile Possibilities solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Letter Tile Possibilities is a medium coding problem on strings, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting, Backtracking
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have a set of letter tiles; tiles[i] is the letter printed on the i-th tile, and several tiles may carry the same letter.
Return the number of distinct non-empty sequences of letters you can spell by laying some of the tiles in a row (each tile at most once). Two sequences are the same when they read the same, regardless of which tiles were used.
Example 1
Input: tiles = "KOK"
Output: 8
Explanation: `K`, `O`, `KK`, `KO`, `OK`, `KKO`, `KOK`, `OKK`.
Example 2
Input: tiles = "ABC"
Output: 15
Explanation: 3 of length one, 6 of length two, 6 of length three.
Example 3
Input: tiles = "Z"
Output: 1
Constraints
1 <= tiles.length <= 7tiles consists of uppercase English letters
Hints for Letter Tile Possibilities
Hint 1
Generating sequences position by position counts duplicates when two tiles share a letter — choose letters, not tiles.
Hint 2
Keep a count per letter. At each step, any letter with a remaining count can be appended.
Hint 3
Every append creates one new distinct sequence; recurse after decrementing that letter's count and restore it afterwards.
How to solve Letter Tile Possibilities
Count distinct sequences by building them letter by letter over the letter counts: each distinct letter choice at each position leads to a distinct sequence, so a DFS over counts enumerates each sequence exactly once.
Approach
- Count how many tiles carry each letter.
- Define
dfs(): for every letter with a positive count, decrement it, add1 + dfs()to the total (the sequence ending here plus all its extensions), and restore the count. - Return
dfs()from the full counts.
Why it works
A sequence is determined by its letters in order, and the DFS branches on the next letter (not the next tile), so two branches always differ in some position and never produce the same sequence; every sequence that the counts allow is reached by following its letters. Equivalently, the answer is the sum over every non-empty sub-multiset of its number of arrangements k! / Π c_i! — a handy cross-check.
Complexity
- Time —
O(answer · 26) — at most 13 699 sequences for seven distinct tiles - Space —
O(n) recursion depth
Pitfalls
- Permuting tiles instead of letters counts
KOKandKOK(with the two K tiles swapped) twice. - The empty sequence does not count.
- Forgetting to restore the count after the recursive call.
Reference solution
Python
def numTilePossibilities(tiles: str) -> int:
count = [0] * 26
for ch in tiles:
count[ord(ch) - 65] += 1
def dfs():
total = 0
for c in range(26):
if count[c] == 0:
continue
count[c] -= 1
total += 1 + dfs()
count[c] += 1
return total
return dfs()Java
public static int numTilePossibilities(String tiles) {
int[] count = new int[26];
for (char ch : tiles.toCharArray()) count[ch - 'A']++;
return tileDfs(count);
}
static int tileDfs(int[] count) {
int total = 0;
for (int c = 0; c < 26; c++) {
if (count[c] == 0) continue;
count[c]--;
total += 1 + tileDfs(count);
count[c]++;
}
return total;
}C++
int tileDfs(vector<int>& count) {
int total = 0;
for (int c = 0; c < 26; c++) {
if (count[c] == 0) continue;
count[c]--;
total += 1 + tileDfs(count);
count[c]++;
}
return total;
}
int numTilePossibilities(string tiles) {
vector<int> count(26, 0);
for (char ch : tiles) count[ch - 'A']++;
return tileDfs(count);
}JavaScript
var numTilePossibilities = function(tiles) {
var count = [];
for (var i = 0; i < 26; i++) count.push(0);
for (var j = 0; j < tiles.length; j++) count[tiles.charCodeAt(j) - 65]++;
var dfs = function() {
var total = 0;
for (var c = 0; c < 26; c++) {
if (count[c] === 0) continue;
count[c]--;
total += 1 + dfs();
count[c]++;
}
return total;
};
return dfs();
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets