Problem Explanation

The problem requests to generate all possible variations of a given string by altering the cases of the letters in the string. The variations of any single character letter is either the letter in lowercase or uppercase. However, the numbers in the string will remain the same in all variations.

For instance, assuming the string is "a1b2". The different case variations will be ["a1b2", "a1B2", "A1b2", "A1B2"].

Walkthrough

Given a string "a1b2", the function checks each character at a time starting from the first. It commences by checking whether the first character is a digit, if it's a digit the function moves to check the next character as digits do not have case variations. If the character is a letter, the function generates both lower case and upper case variations.

The function will generate 2 variations of the original string, it changes the letter to lower case, generates the rest of the possible string variations and appends each to a list of results. Secondly, the function changes the letter to upper case and does the same operation.

Here is an illustration using "ab" string.

Approach

The problem follows a computational model of a Depth First Search (DFS). It utilizes the same strategy of exploring further along with each single path before backtracking. It checks each character if it's a digit it proceeds with the next character, if it's a letter it creates two branches of the tree one for an upper case and another for lower case.

Python Solution

1
2python
3class Solution:
4    def letterCasePermutation(self, S: str) -> List[str]:
5        res = []
6        self.dfs(S, 0, res)
7        return res
8
9    def dfs(self, S, index, res):
10        if index == len(S):
11            res.append(S)
12            return
13        if S[index].isdigit():
14            self.dfs(S, index+1, res)
15            return
16        new_S = list(S)
17        new_S[index] = new_S[index].lower()
18        self.dfs("".join(new_S), index+1, res)
19        new_S[index] = new_S[index].upper()
20        self.dfs("".join(new_S), index+1, res)

Javascript Solution

1
2javascript
3var letterCasePermutation = function(S) {
4    var ans = [];
5    dfs(S, 0);
6    return ans;
7    
8    function dfs(S, i) {
9        if (i === S.length) {
10            ans.push(S);
11            return;
12        }
13        
14        dfs(S, i+1);
15        
16        if (S[i] >= '0' && S[i] <= '9') { 
17          return; 
18        }
19
20        var chs = S.split('');
21        chs[i] = String.fromCharCode(S.charCodeAt(i) ^ (1<<5));
22        dfs(chs.join(''), i+1);
23    }
24};

Java Solution

1
2Java
3class Solution {
4    public List<String> letterCasePermutation(String S) {
5        if (S == null) {
6            return new LinkedList<>();
7        }
8        
9        List<String> res = new LinkedList<>();
10        collect(S.toCharArray(), 0, res);
11        return res;
12    }
13    
14    public void collect(char[] chars, int index, List<String> res) {
15        if (index == chars.length) {
16            res.add(new String(chars));
17        } else {
18            if (Character.isDigit(chars[index])) {
19                collect(chars, index + 1, res);
20                return;
21            }
22            
23            chars[index] = Character.toLowerCase(chars[index]);
24            collect(chars, index + 1, res);
25            
26            chars[index] = Character.toUpperCase(chars[index]);
27            collect(chars, index + 1, res);
28        }
29    }
30}

C# Solution

1
2csharp
3public class Solution {
4    public IList<string> LetterCasePermutation(string S) {
5      	List<string> result = new List<string>();
6        DFS(result,S.ToCharArray(),0);
7        return result;
8    }
9    
10    public void DFS(List<string> result,char[] arr, int i){
11        if(i== arr.Length) {
12            result.Add(new string(arr));
13            return;
14        }
15        if(char.IsLetter(arr[i])){
16            arr[i] = char.ToLower(arr[i]);
17            DFS(result,arr,i+1);
18            arr[i] = char.ToUpper(arr[i]);
19        }
20        DFS(result,arr,i+1);
21    }
22}

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<string> letterCasePermutation(string S) {
6        vector<string> ans;
7        dfs(S, 0, ans);
8        return ans;
9    }
10    
11private:
12    void dfs(string& S, int i, vector<string>& ans) {
13        if (i == S.size()) {
14            ans.push_back(S);
15            return;
16        }
17        dfs(S, i + 1, ans);
18        if (!isdigit(S[i])) {
19            S[i] ^= 32; // Toggle the case
20            dfs(S, i + 1, ans);
21            S[i] ^= 32; // Revert the case change
22        }
23    }
24};

Time Complexity Analysis

Let n be the number of letters in the string S. The problem creates a tree of depth n with each node having two children {lowercase, uppercase}. Hence, time complexity is O(2^n).

However, the problem actually performs better than that in practice, since the time complexity is effectively halved for every digit in the string (as digits don't have any case variations). Also, we have to consider the time taken in creating the strings to add to the result list.

• Python: In Python, strings are immutable, hence every time a case change operation takes place, a new string is created which takes O(n) time, making the overall time complexity O(n*2^n).
• Javascript: Similar to Python, JavaScript strings are also immutable, resulting in the same time complexity, i.e., O(n*2^n).
• Java: Unlike Python and JavaScript, strings are mutable in Java. Thus, no new strings are created in the process and therefore the time complexity reduces to O(2^n).
• C#: Similar to Java, strings are mutable in C#, so the time complexity is again O(2^n).
• C++: C++ complicates this slightly. C++ strings are mutable, so simple case toggling does not create new strings and the operation is O(1), leading to a time complexity of O(2^n). However, when the solution is added to the list, a copy is created which leads to a time complexity of O(n*2^n).

Space Complexity Analysis

The space complexity is influenced by the maximum depth of the recursion stack and the space used by our answer.

Since the recursion depth for this problem is exactly n, hence the space complexity is O(n). The total space used by our answer is proportional to the number of leaf nodes (since each leaf node corresponds to a valid string), which is exactly O(2^n), hence the overall space complexity is O(n + 2^n).

This space complexity holds true for the solution in Python, Javascript, Java, C#, and C++ since they all are using the similar DFS approach for the solution. However, the additional space used for storing the result varies from language to language depending on whether strings are mutable or not.