Letter Case Permutation Problem Statement

Given a string, return all strings that can be generated by changing case of one or more letters in it.

Example One

{
"s": "a1z"
}

Output:

["A1Z", "A1z", "a1Z", "a1z"]

Example Two

{
"s": "123"
}

Output:

["123"]

Notes

Return strings in any order.

Constraints:

• Input string may contain only: 'a'..'z', 'A'..'Z', '0'..'9'
• 1 <= length of the string <= 12

We provided two solutions.

We will start with a recursive approach that generates the expected output and will then move to an iterative solution by looking at an analogy of the output strings with the binary numeral system. Throughout this editorial, we will refer to the length of the given string as length.

Letter Case Permutation Solution 1: Recursive

Let us break the problem into smaller subproblems and see if we can merge the results from the smaller subproblems to reach the result of the original problem.

Suppose we want the letter case permutations of "ab". The first character can become either "A" or "a". If we had the permutations of "b", we could append (prepend) characters "A" and "a" separately to the front of all permutations of "b" to get all the permutations of "ab".

Permutations of "b" are, obviously, ["B", "b"]. Prepending "A" and "a" separately to the front of each of these strings gives us the letter case permutations of "ab": ["AB", "Ab", "aB", "ab"].

Therefore, to get the letter case permutations of any string, we can break the problem into 1) finding all permutations of the string that's shorter by one character (by skipping the first character) and 2) prepending all cases of the first character. If a character in the string has two representations, we will start two separate recursive calls, otherwise (e.g. "1" cannot become anything different by changing its case) we will start only one.

Recursion tree for "ab" is given below.

The {string, integer} pair in each recursive call represents the current state of the string and the starting index of the string under consideration. In each recursive call, we are generating the letter case permutations of the suffix starting at the "starting index". The starting index is initially zero as we initially consider the complete string.

                          {"ab", 0}
               _______________|________________
              |                                |
         {"Ab", 1}                          {"ab", 1}
          ___|___                            ___|___
         |       |                          |       |
     {"AB", 2} {"Ab", 2}               {"aB", 2} {"ab", 2}

We will append the string states into the resultant array when we reach an empty suffix. Therefore, the final array will consist of all the strings present in the leaf nodes of the above recursion tree. For the stated example, it will be: ["AB", "Ab", "aB", "ab"]. We did not discuss the fact that we need the letter case permutations in the lexicographic order.

Time Complexity

O(length * 2^length).

In the worst case, each character is a letter. So there are O(2^length) strings in the output. It takes O(length) time to create and populate a string of length characters.

Auxiliary Space Used

O(length).

We can have at most length number of recursive calls at any moment of time in the call stack; one for each character in the string.

Space Complexity

O(length * 2^length).

Space used for input: O(length).

Auxiliary space used: O(length).

Space used for output: O(length * 2^length).

So, total space complexity is O(length * 2^length).

Code For Letter Case Permutation Solution 1: Recursive

/*
Asymptotic complexity in terms of the length of the input string:
* Time: O(length * 2^length).
* Auxiliary space: O(length).
* Total space: O(length * 2^length).
*/

void populate_permutations_recursively(string &s, int str_index, int length, vector<string> &permutations) {
    if (str_index == length) {
        permutations.push_back(s);
        return;
    }

    // If current character is not a letter, we leave it unchanged and make only one recursive call.
    if (!((s[str_index] >= 'a' and s[str_index] <= 'z') or
          (s[str_index] >= 'A' and s[str_index] <= 'Z'))) {
        populate_permutations_recursively(s, str_index + 1, length, permutations);
        return;
    }

    // Converting current character to uppercase and recursively exploring the
    // remainder of the string.
    s[str_index] = toupper(s[str_index]);
    populate_permutations_recursively(s, str_index + 1, length, permutations);

    // Converting current character to lowercase and recursively exploring the
    // remainder of the string.
    s[str_index] = tolower(s[str_index]);
    populate_permutations_recursively(s, str_index + 1, length, permutations);
}

vector<string> letter_case_permutations(string &s) {
    vector<string> permutations;
    populate_permutations_recursively(s, 0, s.length(), permutations);
    return permutations;
}

Letter Case Permutation Solution 2: Binary Number Analogy

This is not an optimization over the above solution, but it follows a technique that might be useful for you in the other problems that you solve in the future.

A bit in a binary number can either be 0 or 1. An English letter can either be uppercase or lowercase. Let us use this to find the different letter case permutations of the string.

Suppose we have a certain number_of_letters in the string. Total number of the letter case permutations in that case is 2^{numberofletters}. Also, numbers from 0 to 2^{numberofletters} - 1 can be represented using number_of_letters bits. Those numbers have all possible combinations of 0s and 1s for those bits.

We will map each of those number_of_letters bits to exactly one of the English letters in the string. If a bit in a number is a 0, the corresponding character will be kept uppercase, if the bit is a 1 - lowercase.

For "a1bc" we have the following binary numbers and permutations: | Number | Number in Binary | String | ------------- | ------------- | ------------- | | 0 | 000 | A1BC | | 1 | 001 | A1Bc | | 2 | 010 | A1bC | | 3 | 011 | A1bc | | 4 | 100 | a1BC | | 5 | 101 | a1Bc | | 6 | 110 | a1bC | | 7 | 111 | a1bc |

Time Complexity

O(length * 2^length).

In the worst case, each character is a letter. So there are O(2^length) strings in the output. It takes O(length) time to create and populate a string of length characters.

Auxiliary Space Used

O(1).

Space Complexity

O(length * 2^length).

Space used for input: O(length).

Auxiliary space used: O(1).

Space used for output: O(length * 2^length).

So, total space complexity: O(length * 2^length).

Code For Letter Case Permutation Solution 2: Binary Number Analogy

/*
Asymptotic complexity in terms of the length of the input string:
* Time: O(length * 2^length).
* Auxiliary space: O(1).
* Total space: O(length * 2^length).
*/

vector<string> letter_case_permutations(string &s) {
    vector<string> permutations;

    int number_of_letters = 0;
    int len = s.length();

    for (int i = 0; i < len; ++i) {
        if ((s[i] >= 'a' and s[i] <= 'z') or
            (s[i] >= 'A' and s[i] <= 'Z')) {
            number_of_letters++;
        }
    }

    int num_of_permutations = (1 << number_of_letters); // 2 ^ number_of_letters.

    // The mask whose binary equivalent will be used to find the corresponding letter case permutation.
    int current_mask;

    for (int i = 0; i < num_of_permutations; ++i) {
        current_mask = i;
        for (int str_index = len - 1; str_index >= 0; --str_index) {
            if ((s[str_index] >= 'a' and s[str_index] <= 'z') or
                (s[str_index] >= 'A' and s[str_index] <= 'Z')) {
                if ((current_mask & 1) == 0) {
                    s[str_index] = toupper(s[str_index]);
                } else {
                    s[str_index] = tolower(s[str_index]);
                }
                /*
                    We are removing the rightmost bit of current_mask before moving on to the next character.
                    Note that after the following operation, the rightmost bit will correspond to the next
                    character.
                */
                current_mask >>= 1;
            }
        }

        permutations.push_back(s);
    }

    return permutations;
}

We hope that these solutions to letter case permutation have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.