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

[{"language":"Java","code":"class Solution {\n\tpublic List<String> letterC

Related Tags