Problem Statement

Given a string s, generate all possible permutations where the case of each letter is changed. This problem considers only alphabetic characters (ignoring digits and symbols) for case toggling. The order of the characters in the string should remain unchanged, but each letter can independently be either uppercase or lowercase.

Examples

Example 1:

Input: "a1b"
Output: "a1b"
        "A1b"
        "a1B"
        "A1B"

Explanation: The digit 1 is unchanged, while each letter can be in either lowercase or uppercase.

Example 2:

Input: "3z4"
Output: "3z4"
        "3Z4"

Explanation: The numbers 3 and 4 remain unchanged, while the letter z can be in lowercase or uppercase.

Example 3:

Input: "ab"
Output: "ab"
        "aB"
        "Ab"
        "AB"

Explanation: Both letters a and b can independently toggle between lowercase and uppercase.

Example 4:

Input: "XYZ"
Output: "XYZ"
        "XYz"
        "XyZ"
        "xYZ"
        "Xyz"
        "xYz"
        "xyZ"
        "xyz"

Explanation:
Each letter in the input string can be independently change its case.

Different Approaches

1️⃣ Recursion

Intuition:

The problem is about exploring all possible ways to toggle the case of alphabetic characters in a given string while keeping the order of characters unchanged. Each character in the string can be treated as a decision point:

• If it's a digit or symbol, there’s no decision to be made, and the character remains as is.
• If it’s an alphabetic character, there are two possibilities: keep it as lowercase or change it to uppercase.

This suggests a recursive approach where at each step we decide whether to toggle the case of the current alphabetic character or not.

Approach:

1. Use a recursive function that takes the current index and the partially built string as parameters.
2. If the current index reaches the length of the string, add the built string to the result and return.
3. If the character at the current index is a letter, recursively call the function twice:
   • Once without changing the case.
   • Once with the case toggled.
4. If the character is not a letter (like a digit), just move to the next character.
5. Collect all permutations in a result list and return it.

Recursion Tree:

Let's consider a dry run with the input string “a1b”

                                permute(0, "")
                                 /          \
                     permute(1, "a")      permute(1, "A")
                         |                    |
                  permute(2, "a1")       permute(2, "A1")
                   /          \            /        \
      permute(3, "a1b")  permute(3, "a1B")/          \
                                 permute(3, "A1b") permute(3, "A1B")

• Level 0: Start with the empty string and process the character a. We make two recursive calls: one keeping a lowercase and another converting it to uppercase A.
• Level 1: Process 1 (digit), which doesn’t change. Recursively move to the next character.
• Level 2: Process b with both possibilities: lowercase b and uppercase B.
• Level 3: Reached the end, so we add the current permutations to the result.

Final Output: ["a1b", "a1B", "A1b", "A1B"]

Another Recursion Tree for “ABCD”:

Code:

#include <iostream>
#include <vector>
#include <cctype>
using namespace std;

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

    // If the character is a digit, add it as is and move to the next character
    if (isdigit(s[index])) {
        permuteHelper(s, index + 1, current + s[index], result);
    } else {
        // Consider the lowercase version
        permuteHelper(s, index + 1, current + (char)tolower(s[index]), result);
        // Consider the uppercase version
        permuteHelper(s, index + 1, current + (char)toupper(s[index]), result);
    }
}

vector<string> letterCasePermutation(string s) {
    vector<string> result;
    permuteHelper(s, 0, "", result);
    return result;
}

int main() {
    string s = "a1b";
    vector<string> permutations = letterCasePermutation(s);
    
    // Output all permutations
    for (const string &perm : permutations) {
        cout << perm << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2^n), where n is the number of alphabetic characters in the string. Each letter can result in two branches.
• Space Complexity: O(2^n) for storing all the permutations. The recursion depth will be O(n).