Abstract / Summary

Given a string of uppercase letters, count how many different words can be made using all the letters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 84% (300k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Counting
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a single method numTilePossibilities. The method receives a string tiles and computes the number of distinct non-empty sequences that can be formed by arranging any subset of the characters. The algorithm enumerates every possible length, generates all permutations for that length, stores each unique permutation in a set, and finally returns the cardinality of the set.

Core Logic

The first significant step creates a container that automatically discards duplicate entries:

all = set()

The outer loop iterates over every feasible sequence length, starting at one and extending to the full length of the input string:

for i in range(1, len(tiles) + 1):

Inside the loop, the built-in permutations function is invoked to produce every ordering of i characters drawn from tiles. Each permutation is represented as a tuple of characters:

for p in permutations(tiles, i):

Each generated tuple is added to the set, ensuring that only distinct arrangements survive:

all.add(p)

After all lengths have been processed, the method returns the total count of unique permutations:

return len(all)

Edge Cases

When the input string is empty, the range expression range(1, len(tiles) + 1) evaluates to range(1, 1), producing no iterations. Consequently, the set remains empty and the method returns zero, correctly indicating that no non-empty sequences exist.

If the input contains repeated characters, the permutation generator will produce duplicate tuples. Because the results are accumulated in a set, these duplicates are automatically eliminated, guaranteeing that each distinct arrangement is counted exactly once.

The algorithm also gracefully handles strings composed of a single character. The outer loop runs once with i = 1, the inner permutation generator yields a single tuple containing that character, and the set ends up with one element, leading to a return value of one.

Performance Characteristics

The solution leverages Python’s itertools.permutations, a C-level implementation that efficiently produces ordered selections without the overhead of a Python-level recursive generator. By funneling each permutation directly into a set, the code benefits from the average-case constant-time insertion and lookup properties of hash tables, which keeps the deduplication step fast even when many permutations are generated.

Storing permutations as immutable tuples aligns with the requirements of the set data structure, avoiding the need for additional conversion or copying. The approach also avoids explicit recursion, thereby eliminating the risk of deep call stacks for longer input strings.

Overall, the combination of a highly optimized permutation generator and hash-based deduplication yields a solution that scales well for the typical input sizes encountered in practice.

Imagine a box filled with colorful letter tiles. This code is like a game where the computer wants to find every single way to arrange those letters to make different words or patterns.

First, there is a special empty bag called a set. This bag is very smart because it refuses to keep two things that look exactly the same. If the computer tries to put in two identical patterns, the bag just keeps one and ignores the other.

The computer starts by looking at all the tiles. It goes through them to see how many different tiny groups it can make using one tile, then two tiles, and so on until it uses every single piece. For every group it builds, it tucks that pattern into the special bag.

Once the computer finishes looking at every possible combination, it counts how many unique patterns are sitting safely inside the bag. This tells the computer how many different arrangements exist for the letters provided.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: factorial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python				Java			TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python				Java	Go		TS
	LeetcodeHelp	C++	Python				Java
	Progiez	C++	Python				Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai						Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	Garvit244		Python
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	MacJim	C++
	Shamik07								Dart
	suxrobGM				C#
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
Shamik07	Dart
suxrobGM	C#
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality