Jobs

Interviews

Discussions

Letter Case Permutation

Medium

Yelp

0 views

Topics:

StringsRecursion

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 coding it in LeetCode

Letter Case Permutation

Medium

Yelp

0 views

Topics:

StringsRecursion

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 coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Besides letters and digits, can the input string `s` contain other characters like spaces or special symbols?
Is there a maximum length for the input string `s`?
Is the case of the original letters in the input string significant (e.g., should I preserve the original case when generating permutations where a letter remains unchanged)?
Are there any specific ordering requirements for the list of strings returned (e.g., lexicographical order)?

Brute Force Solution

Approach

The goal is to find all possible versions of a string where some letters are uppercase and others are lowercase. Brute force means we'll try absolutely every single combination of upper and lowercase letters.

Here's how the algorithm would work step-by-step:

Start with the original string.
For each letter in the string, consider two options: either leave it as it is, or flip its case (uppercase to lowercase or vice-versa).
If there are no letters, you have one possibility, the original string.
If there is one letter, try both upper and lower cases.
If there are two letters, try all four combinations: both letters unchanged, the first letter changed, the second letter changed, and both letters changed.
Keep creating new versions of the string by considering all possible combinations of case changes for all the letters.
Keep going through all possible options until all characters in the entire string have been considered. In the end, we have generated a list of all possible permutations of upper and lower case variations for the string.

Code Implementation

def letter_case_permutation(input_string):
    possible_permutations = []

    def backtrack(current_string, index):
        # Base case: If we've processed all characters, add the permutation
        if index == len(input_string):
            possible_permutations.append(current_string)
            return

        current_character = input_string[index]

        # If the character is a digit, simply proceed to the next character
        if current_character.isdigit():
            backtrack(current_string + current_character, index + 1)
        else:
            # Explore both lowercase and uppercase options

            # First convert to lowercase
            backtrack(current_string + current_character.lower(), index + 1)

            # Then convert to uppercase
            backtrack(current_string + current_character.upper(), index + 1)

    backtrack("", 0)
    return possible_permutations

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible letter case combinations of the input string. For each character in the string of length n, there are two choices: either keep its original case or flip it. This branching results in a binary tree-like exploration, where each level corresponds to a character and each branch represents a case choice. Therefore, the total number of possible permutations (leaves of the tree) is 2 raised to the power of n (2^n). Constructing each permutation also takes O(n) time, so technically the complete time complexity could be considered O(n * 2^n). However, the dominant factor is the number of permutations, which is 2^n, thus, the time complexity is O(2^n).

Space Complexity

O(2^N) – The algorithm generates all possible letter case permutations of the input string. In the worst-case scenario, where all characters are letters, each character has two possibilities (uppercase or lowercase). This leads to 2^N possible permutations, where N is the length of the input string. The algorithm stores each of these permutations in a list or similar data structure, resulting in an auxiliary space proportional to the number of permutations. Therefore, the space complexity is O(2^N).

Optimal Solution

Approach

The trick is to think about building the possible results one character at a time. When we see a letter, we branch out and create two possibilities: one where the letter is uppercase and one where it's lowercase. We continue building on each of these possibilities until we have explored every letter in the input string.

Here's how the algorithm would work step-by-step:

Start with an empty result.
Go through the input string, character by character.
If the current character is a letter, create two new results for each existing result: one with the letter in uppercase and one with the letter in lowercase. Replace the previous result with these two.
If the current character is a number, simply add the number to each existing result.
Repeat these steps for every character in the input string.
The final set of results will contain all the letter case permutations.

Code Implementation

def letter_case_permutation(input_string):
    possible_permutations = [""]

    for character in input_string:
        # Branch to handle upper/lower case for letters
        if character.isalpha():

            new_permutations = []
            for permutation in possible_permutations:
                new_permutations.append(permutation + character.lower())
                new_permutations.append(permutation + character.upper())
            possible_permutations = new_permutations

        # Non-letters are added to all existing permutations.
        else:
            for index in range(len(possible_permutations)):
                possible_permutations[index] += character

    return possible_permutations

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through the input string of length n. For each letter, it doubles the number of existing partial permutations. In the worst case, where all characters are letters, the number of permutations grows exponentially. Therefore, the total number of permutations generated is 2 raised to the power of the number of letters, which can be at most n. Thus, the time complexity is O(2^n).

Space Complexity

O(2^N) – The algorithm maintains a list of results that grows with each letter in the input string. For each letter encountered, the number of results doubles, creating two new results from each existing one. In the worst case, where all characters are letters, the number of results will be 2^N, where N is the length of the input string. Therefore, the space required to store these results is proportional to 2^N, dominating the space complexity. Other space usages such as character variables are negligible compared to the list of results.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list immediately, as there are no permutations to generate.
String with only digits	Return a list containing only the original string, as there are no letters to permute.
String with only one character (letter)	Return a list containing both the uppercase and lowercase versions of the character.
String with mixed case letters and digits	The solution should correctly handle both uppercase and lowercase letters and ignore digits.
Maximum length string (consider recursion depth or memory usage)	The solution should be designed to be space and time efficient and avoid excessive recursion depth for very long strings.
String with special characters	The provided constraints specify only letters and digits, so special characters should be explicitly handled by either throwing an exception or ignoring them in the permutation process.
String with all the same letters (e.g., 'aaaa')	The solution should still generate all possible case permutations even with repeated identical letters.
Case sensitivity differences affecting permutations (e.g. 'aA')	The solution should ensure each letter, regardless of the initial case, can be either uppercase or lowercase in the permutations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null?
Besides letters and digits, can the input string `s` contain other characters like spaces or special symbols?
Is there a maximum length for the input string `s`?
Is the case of the original letters in the input string significant (e.g., should I preserve the original case when generating permutations where a letter remains unchanged)?
Are there any specific ordering requirements for the list of strings returned (e.g., lexicographical order)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the original string.
For each letter in the string, consider two options: either leave it as it is, or flip its case (uppercase to lowercase or vice-versa).
If there are no letters, you have one possibility, the original string.
If there is one letter, try both upper and lower cases.
If there are two letters, try all four combinations: both letters unchanged, the first letter changed, the second letter changed, and both letters changed.
Keep creating new versions of the string by considering all possible combinations of case changes for all the letters.
Keep going through all possible options until all characters in the entire string have been considered. In the end, we have generated a list of all possible permutations of upper and lower case variations for the string.

Code Implementation

def letter_case_permutation(input_string):
    possible_permutations = []

    def backtrack(current_string, index):
        # Base case: If we've processed all characters, add the permutation
        if index == len(input_string):
            possible_permutations.append(current_string)
            return

        current_character = input_string[index]

        # If the character is a digit, simply proceed to the next character
        if current_character.isdigit():
            backtrack(current_string + current_character, index + 1)
        else:
            # Explore both lowercase and uppercase options

            # First convert to lowercase
            backtrack(current_string + current_character.lower(), index + 1)

            # Then convert to uppercase
            backtrack(current_string + current_character.upper(), index + 1)

    backtrack("", 0)
    return possible_permutations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty result.
Go through the input string, character by character.
If the current character is a letter, create two new results for each existing result: one with the letter in uppercase and one with the letter in lowercase. Replace the previous result with these two.
If the current character is a number, simply add the number to each existing result.
Repeat these steps for every character in the input string.
The final set of results will contain all the letter case permutations.

Code Implementation

def letter_case_permutation(input_string):
    possible_permutations = [""]

    for character in input_string:
        # Branch to handle upper/lower case for letters
        if character.isalpha():

            new_permutations = []
            for permutation in possible_permutations:
                new_permutations.append(permutation + character.lower())
                new_permutations.append(permutation + character.upper())
            possible_permutations = new_permutations

        # Non-letters are added to all existing permutations.
        else:
            for index in range(len(possible_permutations)):
                possible_permutations[index] += character

    return possible_permutations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list immediately, as there are no permutations to generate.
String with only digits	Return a list containing only the original string, as there are no letters to permute.
String with only one character (letter)	Return a list containing both the uppercase and lowercase versions of the character.
String with mixed case letters and digits	The solution should correctly handle both uppercase and lowercase letters and ignore digits.
Maximum length string (consider recursion depth or memory usage)	The solution should be designed to be space and time efficient and avoid excessive recursion depth for very long strings.
String with special characters	The provided constraints specify only letters and digits, so special characters should be explicitly handled by either throwing an exception or ignoring them in the permutation process.
String with all the same letters (e.g., 'aaaa')	The solution should still generate all possible case permutations even with repeated identical letters.
Case sensitivity differences affecting permutations (e.g. 'aA')	The solution should ensure each letter, regardless of the initial case, can be either uppercase or lowercase in the permutations.