Letter Case Permutation
MediumUpdated: Sep 18, 2025
Practice on:
Problem
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.
Return a list of all possible strings we could create. Return the output in any order.
Examples
Example 1
Input:
s = "a1b2"
Output:
["a1b2","a1B2","A1b2","A1B2"]
Example 2
Input:
s = "3z4"
Output:
["3z4","3Z4"]
Example 3
Input: s = "ab"
Output: ["ab","aB","Ab","AB"]
Solution
Method 1 - Backtracking OR DFS Solution
Let's build the space tree:
Recursion Tree (Mermaid)
graph TD A0["A(a1b2,0)"] A1["A(a1b2,1)"] A2["A(A1b2,1)"] B1["A(a1b2,2)"] B2["A(A1b2,2)"] C1["A(a1b2,3)"] C2["A(a1B2,3)"] C3["A(A1b2,3)"] C4["A(A1B2,3)"] D1["A(a1b2,4)"] D2["A(a1B2,4)"] D3["A(A1b2,4)"] D4["A(A1B2,4)"] A0 -- "a" --> A1 A0 -- "A" --> A2 A1 -- "1" --> B1 A2 -- "1" --> B2 B1 -- "b" --> C1 B1 -- "B" --> C2 B2 -- "b" --> C3 B2 -- "B" --> C4 C1 -- "2" --> D1 C2 -- "2" --> D2 C3 -- "2" --> D3 C4 -- "2" --> D4 %% Leaves: D1, D2, D3, D4 are valid permutations
// During this process, we are changing the S char array itself
Code
Java
class Solution {
public List<String> letterCasePermutation(String S) {
List<String> ans = new ArrayList<>();
backtrack(S.toCharArray(), 0, ans);
return ans;
}
private void backtrack(char[] chars, int i, List<String> ans) {
if (i == chars.length) {
ans.add(new String(chars));
return;
}
if (Character.isLetter(chars[i])) {
chars[i] = Character.toUpperCase(chars[i]);
backtrack(chars, i + 1, ans);
chars[i] = Character.toLowerCase(chars[i]);
backtrack(chars, i + 1, ans);
} else {
backtrack(chars, i + 1, ans);
}
}
}
Python
class Solution:
def letterCasePermutation(self, S: str) -> list[str]:
ans = []
def backtrack(chars: list[str], i: int):
if i == len(chars):
ans.append(''.join(chars))
return
if chars[i].isalpha():
chars[i] = chars[i].upper()
backtrack(chars, i + 1)
chars[i] = chars[i].lower()
backtrack(chars, i + 1)
else:
backtrack(chars, i + 1)
backtrack(list(S), 0)
return ans
Go
func letterCasePermutation(S string) []string {
var ans []string
var backtrack func(chars []byte, i int)
backtrack = func(chars []byte, i int) {
if i == len(chars) {
ans = append(ans, string(chars))
return
}
if (chars[i] >= 'a' && chars[i] <= 'z') || (chars[i] >= 'A' && chars[i] <= 'Z') {
chars[i] = byte(unicode.ToUpper(rune(chars[i])))
backtrack(chars, i+1)
chars[i] = byte(unicode.ToLower(rune(chars[i])))
backtrack(chars, i+1)
} else {
backtrack(chars, i+1)
}
}
backtrack([]byte(S), 0)
return ans
}
Kotlin
class Solution {
fun letterCasePermutation(S: String): List<String> {
val ans = mutableListOf<String>()
fun backtrack(chars: CharArray, i: Int) {
if (i == chars.size) {
ans.add(String(chars))
return
}
if (chars[i].isLetter()) {
chars[i] = chars[i].uppercaseChar()
backtrack(chars, i + 1)
chars[i] = chars[i].lowercaseChar()
backtrack(chars, i + 1)
} else {
backtrack(chars, i + 1)
}
}
backtrack(S.toCharArray(), 0)
return ans
}
}
Rust
impl Solution {
pub fn letter_case_permutation(s: String) -> Vec<String> {
fn backtrack(chars: &mut [u8], i: usize, ans: &mut Vec<String>) {
if i == chars.len() {
ans.push(String::from_utf8(chars.to_vec()).unwrap());
return;
}
if chars[i].is_ascii_alphabetic() {
chars[i] = chars[i].to_ascii_uppercase();
backtrack(chars, i + 1, ans);
chars[i] = chars[i].to_ascii_lowercase();
backtrack(chars, i + 1, ans);
} else {
backtrack(chars, i + 1, ans);
}
}
let mut ans = Vec::new();
let mut chars = s.into_bytes();
backtrack(&mut chars, 0, &mut ans);
ans
}
}
TypeScript
class Solution {
letterCasePermutation(S: string): string[] {
const ans: string[] = [];
function backtrack(chars: string[], i: number) {
if (i === chars.length) {
ans.push(chars.join(''));
return;
}
if (/[a-zA-Z]/.test(chars[i])) {
chars[i] = chars[i].toUpperCase();
backtrack(chars, i + 1);
chars[i] = chars[i].toLowerCase();
backtrack(chars, i + 1);
} else {
backtrack(chars, i + 1);
}
}
backtrack(S.split(''), 0);
return ans;
}
}
Method 2 - BFS and Iterative
Intuition
Instead of using recursion, we can use a queue to iteratively build all possible permutations. At each character, if it's a letter, we branch into two cases (uppercase and lowercase) for every string currently in the queue. This approach is similar to BFS, and the ASCII figure below shows how the permutations grow level by level:
abc
abc Abc // after processing index 0
abc aBc Abc ABc // after processing index 1
abc abC aBc aBC Abc AbC ABc ABC // after processing index 2
Each level represents processing a character in the string. For digits, we simply continue; for letters, we branch.
Approach
- Initialize a queue with the original string.
- For each character in the string:
- If it's a digit, continue.
- If it's a letter, for each string in the queue, branch into uppercase and lowercase at the current position.
- After processing all characters, the queue contains all permutations.
Complexity
- ⏰ Time complexity:
O(N * 2^L)— Where N is the length of the string and L is the number of letters. Each letter doubles the number of permutations. - 🧺 Space complexity:
O(2^L)— The queue stores all possible permutations.
Code
Java
class Solution {
public List<String> letterCasePermutation(String S) {
if (S == null) return new LinkedList<>();
Queue<String> queue = new LinkedList<>();
queue.offer(S);
for (int i = 0; i < S.length(); i++) {
if (Character.isDigit(S.charAt(i))) continue;
int size = queue.size();
for (int j = 0; j < size; j++) {
String cur = queue.poll();
char[] chs = cur.toCharArray();
chs[i] = Character.toUpperCase(chs[i]);
queue.offer(String.valueOf(chs));
chs[i] = Character.toLowerCase(chs[i]);
queue.offer(String.valueOf(chs));
}
}
return new LinkedList<>(queue);
}
}
Python
from collections import deque
class Solution:
def letterCasePermutation(self, S: str) -> list[str]:
queue = deque([S])
for i in range(len(S)):
if S[i].isdigit():
continue
size = len(queue)
for _ in range(size):
cur = queue.popleft()
chars = list(cur)
chars[i] = chars[i].upper()
queue.append(''.join(chars))
chars[i] = chars[i].lower()
queue.append(''.join(chars))
return list(queue)
Go
func letterCasePermutation(S string) []string {
queue := []string{S}
for i := 0; i < len(S); i++ {
if S[i] >= '0' && S[i] <= '9' {
continue
}
size := len(queue)
for j := 0; j < size; j++ {
cur := queue[0]
queue = queue[1:]
chars := []byte(cur)
chars[i] = byte(unicode.ToUpper(rune(chars[i])))
queue = append(queue, string(chars))
chars[i] = byte(unicode.ToLower(rune(chars[i])))
queue = append(queue, string(chars))
}
}
return queue
}
Kotlin
class Solution {
fun letterCasePermutation(S: String): List<String> {
val queue = ArrayDeque<String>()
queue.add(S)
for (i in S.indices) {
if (S[i].isDigit()) continue
repeat(queue.size) {
val cur = queue.removeFirst()
val chars = cur.toCharArray()
chars[i] = chars[i].uppercaseChar()
queue.add(String(chars))
chars[i] = chars[i].lowercaseChar()
queue.add(String(chars))
}
}
return queue.toList()
}
}
Rust
impl Solution {
pub fn letter_case_permutation(s: String) -> Vec<String> {
let mut queue = std::collections::VecDeque::new();
queue.push_back(s.clone());
for i in 0..s.len() {
if s.as_bytes()[i].is_ascii_digit() {
continue;
}
let size = queue.len();
for _ in 0..size {
let cur = queue.pop_front().unwrap();
let mut chars = cur.into_bytes();
chars[i] = chars[i].to_ascii_uppercase();
queue.push_back(String::from_utf8(chars.clone()).unwrap());
chars[i] = chars[i].to_ascii_lowercase();
queue.push_back(String::from_utf8(chars).unwrap());
}
}
queue.into_iter().collect()
}
}
TypeScript
class Solution {
letterCasePermutation(S: string): string[] {
let queue: string[] = [S];
for (let i = 0; i < S.length; i++) {
if (/[0-9]/.test(S[i])) continue;
const size = queue.length;
for (let j = 0; j < size; j++) {
const cur = queue.shift()!;
const chars = cur.split('');
chars[i] = chars[i].toUpperCase();
queue.push(chars.join(''));
chars[i] = chars[i].toLowerCase();
queue.push(chars.join(''));
}
}
return queue;
}
}