King Of Interviews

Letter Case Permutation: 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.

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 12
s consists of lowercase English letters, uppercase English letters, and digits.

Try this Problem on your own or check similar problems:

Solution:

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<String>();
        helper(0, new char[s.length()], s, result);
        return result;
    }

    private void helper(int index, char[] currentWord, String word, List<String> list){
        if(index == word.length()){
            list.add(new String(currentWord));
            return;
        }
        char c = word.charAt(index);
        if(Character.isDigit(c)){
            currentWord[index] = c;
            helper(index + 1, currentWord, word, list);
        }
        else{
            currentWord[index] = Character.toLowerCase(c);
            helper(index + 1, currentWord, word, list);
            currentWord[index] = Character.toUpperCase(c);
            helper(index + 1, currentWord, word, list);
        }
    }
}

Time/Space Complexity:

Time Complexity: O(L*2^L)
Space Complexity: O(L)

Explanation:

Most of the backtracking problems can be solved using the following format:

we define the result list that will be passed to the helper function
we define current position (in matrix, string…) and also the default value for the value that we want to generate inside the helper function (e.g. currentWord)
we define the helper function where we will have our base case (e.g. index == word.length())) and then we do decision making defined by the problem statement and recursively call helper function (often while iterating over array)

This problem is no different, we define our result list, set the current index to 0 and pass the structure to hold the value we will be generating to the helper function (in our case currentWord). In helper function we check first for the base case (if we have a currentWord which has the same length as our input word word) and if the base case is fulfilled, we just add the current word to our result list and return from the helper function (no point going forward with recursion since index will be larger than the length of input word). Now to the decision making, we have the following:

if the current character is a digit, we keep it as it is and go deeper into building the word (index+1)
if the current character is a letter we have two choices: either make it upperCase or lowerCase. We try both and go select the next character (until we reach index == word.length()).

For the main function we then return the result list containing all permutations of string. The space complexity will be equal to the recursion stack where depth is equal to word length, while time complexity is O(L*2^L) (L is length of the input word), because we have L decisions to make (depth of recursion stack) and for each decision we take at most 2 choices (e.g. upperCase and lowerCase) making the breadth equal to 2. The L multiplier comes from creating a string from array of characters (list.add(new String(currentWord));).

Letter Case Permutation