About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Letter Case Permutations Problem

Return the set of strings which can be generated from a given string by changing the case of a group of letter(s).

Return all the possible strings in lexicographic order.

Example One:

Input: “a1z”

Output: [“A1Z”, “A1z”, “a1Z”, “a1z”]

Example Two:

Input: “123”

Output: [“123”]

Notes:

Constraints:

● 1

● The string may contain the following ASCII characters only: ‘a’..’z’, ‘A’..’Z’, ‘0’..’9’

Solution

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 number system. Throughout this editorial, we will refer to the input string as str and its length as length.

1) recursively_generaring_permutations_solution.cpp

Let us try breaking our problem into smaller subproblems and see if we could merge the results from the smaller subproblems to reach the result of our original problem.

Suppose we want the letter case permutations of the string “ab”. The first character ‘a’ in the string can be represented either by ‘A’ or ‘a’. So, if we had the letter case permutations of the string “b”, we could push ‘A’ and ‘a’ separately to the front of all the letter case permutations of “b” to get the letter case permutations of the string “ab”.

The letter case permutations of the string “b” will be [“B”, “b”].

Pushing ‘A’ and ‘a’ separately to the front of each of these strings gives us the letter case permutations of “ab” as [“AB”, “Ab”, “aB”, “ab”].

Therefore, to get the letter case permutations of any string, we can break our problem to finding the letter case permutations of the string with one character less (by skipping the first character). If a character in the string can have two possible representations, we will have two separate recursive calls to include both the possibilities of that character.

The recursion tree for the above example will thus look like 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. How can we maintain that?

The string “A” is lexicographically smaller than the string “a”. While branching out to the next suffix, we have two options to consider for the first character of the current suffix. Setting the character to uppercase before setting it to lowercase will ensure that we are getting the permutations in lexicographical order.

Time Complexity:

O(length * 2length).

In the worst case, each character in the string might be an English alphabet. In that case, we will have to consider two possibilities of all the length numbers of characters present in the string. So, the total number of possible output strings will be O(2length). It will take O(length) amount of time to copy each of these strings into our result. This makes the overall time complexity equal to O(length * 2length).

Auxiliary Space Used:

O(length).

We can have at most a length number of recursive calls at any moment of time in the recursion stack (one for each character in the string).

Space Complexity:

Space used for input: O(length).

Auxiliary space used: O(length).

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

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


// -------- START --------

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

    // If the current character is not an English alphabet, we must not change it.
    if (!((str[str_index] >= 'a' and str[str_index] <= 'z') or
            (str[str_index] >= 'A' and str[str_index] <= 'Z')))
    {
        get_permutations(str, str_index + 1, length, permutations);
        return;
    }

    // Converting the character to uppercase and recursively exploring the
    // letter case permuations of string str[str_index + 1 ... length - 1].
    str[str_index] = toupper(str[str_index]);
    get_permutations(str, str_index + 1, length, permutations);

    // Converting the character to lowercase and recursively exploring the
    // letter case permuations of string str[str_index + 1 ... length - 1].
    str[str_index] = tolower(str[str_index]);
    get_permutations(str, str_index + 1, length, permutations);
}

vector < string > letter_case_permutations(string str) {
    vector < string > permutations;
    get_permutations(str, 0, str.length(), permutations);

    return permutations;
}

// -------- END --------

2) binary_number_analogy_solution.cpp

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.

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

Suppose we have an alphabet_count number of english alphabets in str. The number of different letter case permutations will be 2alphabet_count (as we will have 2 ways to represent each of those alphabet_count characters).

Also, the binary numbers from 0 to 2alphabet_count - 1 can be represented using alphabet_count bits each and these will have all the possible combinations of 0s and 1s for those bits.

So, we will map exactly one of those alphabet_count bits to exactly one of the English alphabets present in the string. If a bit in a number is 0, the corresponding character will be kept uppercase. Whereas, if the bit is 1, the corresponding character will be kept lowercase.

Suppose we have str = “a1bc”, this method will generate the following strings for the different binary numbers:

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

Note that the strings in the table are automatically generated in the lexicographic order. How?

For any English character in the string, we want to prioritize the occurrence of its uppercase version over its lowercase version. Also, if we consider the binary numbers in ascending order, 0 is prioritized automatically over 1 for any bit position. Therefore, representing uppercase characters by 0 and lowercase characters by 1 automatically prioritizes the uppercase characters over the lowercase characters. Hence, the strings are automatically generated in the lexicographic order.

Time Complexity:

O(length * 2length).

In the worst case, all the characters in the string might be an English alphabet. In that case, 2length numbers of permutations are generated and it takes O(length) time to generate each permutation. So, the total time complexity is O(length * 2length).

Auxiliary Space Used:

O(1).

We needed a constant amount of additional memory.

Space Complexity:

Space used for input: O(length).

Auxiliary space used: O(1).

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

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


// -------- START --------

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

    // If the current character is not an English alphabet, we must not change it.
    if (!((str[str_index] >= 'a' and str[str_index] <= 'z') or
            (str[str_index] >= 'A' and str[str_index] <= 'Z')))
    {
        get_permutations(str, str_index + 1, length, permutations);
        return;
    }

    // Converting the character to uppercase and recursively exploring the
    // letter case permuations of string str[str_index + 1 ... length - 1].
    str[str_index] = toupper(str[str_index]);
    get_permutations(str, str_index + 1, length, permutations);

    // Converting the character to lowercase and recursively exploring the
    // letter case permuations of string str[str_index + 1 ... length - 1].
    str[str_index] = tolower(str[str_index]);
    get_permutations(str, str_index + 1, length, permutations);
}

vector < string > letter_case_permutations(string str) {
    vector < string > permutations;
    get_permutations(str, 0, str.length(), permutations);

    return permutations;
}

// -------- END --------