algoadvance

Leetcode 784. Letter Case Permutation

Problem Statement

Leetcode Problem 784: Letter Case Permutation

Given a string s, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Example

• Input: s = "a1b2"
• Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Constraints

• s will be a string with length between 1 and 12.
• s will consist only of letters and digits.

Clarifying Questions

1. Does the transformation affect non-letter characters (e.g., digits)?
   • No, only letters (both lowercase and uppercase) are transformed.
2. Is there an expected order in the output permutations?
   • No specific order is required for the output permutations.
3. What should be returned if the input string contains no letters?
   • The output should be a list containing the original string itself.

Strategy

1. Backtracking Approach:
   • Use a recursive backtracking approach to explore all possible transformations of the input string.
   • For each character in the string, decide whether to:
     • Keep the character as is (if it’s a digit).
     • Convert the character to both lowercase and uppercase and continue the search.
   • Collect all transformed strings into a result list.

Code

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> result;
        backtrack(s, 0, "", result);
        return result;
    }

private:
    void backtrack(string &s, int index, string current, vector<string> &result) {
        if (index == s.size()) {
            result.push_back(current);
            return;
        }

        char c = s[index];
        if (isalpha(c)) {
            // Choice 1: Keep the current character in lowercase
            backtrack(s, index + 1, current + (char)tolower(c), result);
            // Choice 2: Change the current character to uppercase
            backtrack(s, index + 1, current + (char)toupper(c), result);
        } else {
            // If the character is not a letter, keep it as is
            backtrack(s, index + 1, current + c, result);
        }
    }
};

Time Complexity

• Time Complexity:
  • The time complexity of the backtracking approach is (O(2^N)), where (N) is the number of letters in the string s. This is because each letter can be either in lowercase or uppercase, hence there are (2^N) possible combinations.
• Space Complexity:
  • The space complexity is also (O(2^N \cdot N)) due to the storage of each permutation which can have at most (2^N) permutations of length (N). The recursion depth can go up to (N) as well.

This solution should be efficient enough given the constraint that (s) can have a maximum length of 12.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?