Abstract / Summary

Given a string, output all possible strings by changing each letter to lowercase or uppercase.

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 76% (400k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Bit Manipulation
• 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 solves the problem of generating all possible strings that can be formed by toggling the case of each alphabetic character in the input string. It builds the result iteratively, expanding a set of partial strings with each character from the input. The final set contains every permutation where each letter may appear in either lower-case or upper-case form.

Core Logic

The algorithm starts by initializing a set that holds a single empty string. This set represents the collection of partial results built so far.

dp = set([""])

For each character c in the input string, a new temporary set is created. The algorithm iterates over every string currently stored in dp and appends two versions of the character to each string: one forced to lower-case and one forced to upper-case. Both versions are added to the temporary set.

for c in s:
    next = set()
    for i in dp:
        next.add(i + c.lower())
        next.add(i + c.upper())
    dp = next

After processing all characters, the set dp holds every possible case permutation. The method returns this set directly.

return dp

The use of a set guarantees that duplicate strings are automatically eliminated, which can happen when the input contains characters that are not alphabetic (for example, digits or symbols). In such cases, c.lower() and c.upper() produce identical results, and the set collapses the duplicates, ensuring the output contains each unique permutation exactly once.

Edge Cases Handled

When the input string contains non-alphabetic characters, the lower-case and upper-case transformations yield the same character. The inner loop still attempts to add both versions, but because the container is a set, only one copy persists. This behavior naturally handles inputs that mix letters with numbers, punctuation, or whitespace without requiring explicit conditional checks.

If the input string is empty, the initial set contains only the empty string. The outer loop does not execute, and the method returns a set with a single empty string, which correctly represents the only permutation of an empty input.

The algorithm also gracefully processes strings that consist entirely of letters, digits, or any combination thereof. The case conversion functions are applied uniformly, and the set semantics ensure that the final collection reflects the correct number of distinct permutations.

Performance Optimizations

The implementation leverages a set for both intermediate and final storage. This choice provides constant-time membership checks and automatic deduplication, which eliminates the need for additional logic to filter out repeated entries. By reassigning dp to the newly built set after each character, the code discards the previous collection, allowing the Python garbage collector to reclaim memory that is no longer needed.

Using c.lower() and c.upper() directly on each character avoids the overhead of conditional branching based on character type. The functions are built-in and highly optimized, ensuring that the case conversion step incurs minimal cost.

The iterative approach builds each permutation exactly once, avoiding recursive call overhead and stack usage. This results in a straightforward control flow that scales linearly with the length of the input string while the number of generated strings grows exponentially, as dictated by the problem definition. The use of a set also means that the final return value is already in a hash-based container, which can be advantageous for callers that need fast lookup of the generated permutations.

Imagine you have a box of magic letters. Every time you pick up a letter, it has a special power to change its shape. Sometimes it wants to be a tiny lowercase letter, and sometimes it wants to be a big uppercase letter.

This code starts with an empty list to hold combinations. It looks at the string one letter at a time. For every letter it finds, it takes all the combinations it has made so far and tries two new things. It takes the current combination and adds the small version of the letter to it, and then it also takes the same combination and adds the big version of the letter to it instead.

It keeps doing this for every single letter in the string. If the string is cat, it starts with an empty space and builds up. First, it makes c and C. Then it takes those and adds a to make ca, Ca, cA, and CA. Finally, it adds t to make all the possible ways you could write that word with different sizes for each letter. By the time it reaches the end, it has a collection of every possible mix of big and small letters that could be formed from the original word.

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

Time: exponential
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++	Java	Python						TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python			Rust		Go	TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem							Ruby
	fengvyi	C++
	gouthampradhan		Java
	halfrost								Go
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	lzl124631x	C++
	qiyuangong		Java
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
lzl124631x	C++
qiyuangong	Java
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
zfang399	C++

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