Letter Case Permutation

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:

1
2
3
4


Input:
s = "a1b2"
Output:
 ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

1
2
3
4


Input:
s = "3z4"
Output:
 ["3z4","3Z4"]

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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);
		}
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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:

1
2
3
4


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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;
	}
}

Problem#

Examples#

Solution#

Method 1 - Backtracking OR DFS Solution#

Recursion Tree (Mermaid)#

Code#

Method 2 - BFS and Iterative#

Intuition#

Approach#

Complexity#

Code#

Problem

Examples

Solution

Method 1 - Backtracking OR DFS Solution

Recursion Tree (Mermaid)

Code

Method 2 - BFS and Iterative

Intuition

Approach

Complexity

Code