algoadvance

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. You can return the output in any order.

Examples:

1. Input: s = “a1b2” Output: [“a1b2”, “a1B2”, “A1b2”, “A1B2”]

2. Input: s = “3z4” Output: [“3z4”, “3Z4”]

3. Input: s = “12345” Output: [“12345”]

Clarifying Questions

1. Q: Does the string contain only alphanumeric characters? A: Yes, the string s contains only letters and digits.

2. Q: Is there a specific order required for the output strings? A: No, the output strings can be in any order.

3. Q: Can the input string be empty? A: The prompt does not mention it explicitly, but typically for an empty string the output would be a list containing an empty string: [""].

Strategy

To solve this problem, we can use a backtracking approach:

1. Iterate through each character in the string.
2. If the character is a digit, it remains the same.
3. If the character is a letter, explore both possibilities: it being lowercase and uppercase.
4. Use recursion to build permutations for subsequent characters and combine them to form the complete list of permutations.

Code

def letterCasePermutation(s):
    def backtrack(sub_s, index):
        if index == len(s):
            result.append(sub_s)
            return
            
        if s[index].isdigit():
            backtrack(sub_s + s[index], index + 1)
        else:
            backtrack(sub_s + s[index].lower(), index + 1)
            backtrack(sub_s + s[index].upper(), index + 1)
    
    result = []
    backtrack("", 0)  # Initially start with an empty substring and index 0
    return result

# Example usage:
print(letterCasePermutation("a1b2"))  # ["a1b2", "a1B2", "A1b2", "A1B2"]
print(letterCasePermutation("3z4"))   # ["3z4", "3Z4"]
print(letterCasePermutation("12345")) # ["12345"]

Time Complexity

• Time Complexity: O(2^N) where N is the number of letters in the input string s. Each letter can have 2 states (lowercase or uppercase), leading to 2^N combinations. Digits do not contribute to the exponential increase.
• Space Complexity: O(2^N) to store the result list as we may generate up to 2^N permutations. Additionally, the recursion call stack will use O(N) space.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?