We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Letter Case Permutation

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires generating all combinations of a string where each letter can be either lowercase or uppercase.
  • Non-letter characters (digits) remain unchanged during the transformation.
  • The maximum length of the string is 12, making it feasible to use a backtracking approach or bit manipulation to explore all combinations.

Space and Time Complexity

Time Complexity: O(2^n), where n is the number of letters in the string. Each letter can be transformed in two ways, leading to 2^n combinations. Space Complexity: O(n), for storing the current path during recursion and the final result list.

Solution

To solve the problem, we can use a backtracking approach. We will iterate through each character of the string:

  • If the character is a letter, we will make two recursive calls: one with the lowercase version and another with the uppercase version.
  • If the character is a digit, we simply add it to the current combination.
  • Once we reach the end of the string, we add the current combination to the result list.

We will use a list to store the current combination and a final list to store all results.

Code Solutions

def letterCasePermutation(s: str):
    def backtrack(index: int, path: str):
        if index == len(s):
            result.append(path)
            return
        # Process current character
        if s[index].isalpha():
            # Choose lowercase
            backtrack(index + 1, path + s[index].lower())
            # Choose uppercase
            backtrack(index + 1, path + s[index].upper())
        else:
            # If it's a digit, just add it
            backtrack(index + 1, path + s[index])
    
    result = []
    backtrack(0, "")
    return result
← Back to All Questions