784. Letter Case Permutation

MediumBit ManipulationStringBacktracking

Problem Description

In this problem, we're given a string s consisting of alphabetical characters. We have the freedom to change each of these characters individually to either lowercase or uppercase, which can lead to various permutations of the string with different cases for each letter. The task is to generate all possible strings with these different case transformations and return them as a list in any order.

An example to illustrate this: for the string "a1b2", the output will be ["a1b2", "a1B2", "A1b2", "A1B2"].

This is a typical backtracking problem, as we'll consider each character and explore the possibilities of both keeping it as it is or changing its case, accumulating all different strings that can be formed by these choices.

Flowchart Walkthrough

Let's use the algorithm flowchart to analyze the problem described in LeetCode 784, Letter Case Permutation. Here's a step-by-step walkthrough using the Flowchart:

Is it a graph?

No: The problem is not about nodes and edges as in graph-based problems.

Need to solve for kth smallest/largest?

No: The problem entails generating permutations, not finding a specific order statistic.

Involves Linked Lists?

No: The problem involves strings, not data structures such as linked lists.

Does the problem have small constraints?

Yes: The string size is usually manageable, which allows exploring all character case permutations without extreme computational cost.

Brute force / Backtracking?

Yes: The problem requires generating all variations of the string with upper and lower case characters, which is well-suited for a backtracking approach.

Conclusion: The flowchart suggests using the backtracking technique to explore all possible case permutations of the input string, adjusting each character between lowercase and uppercase and recursively proceeding to construct all combinations.

Intuition

To achieve our solution, we can apply a method known as depth-first search (DFS), which is a type of backtracking algorithm. The DFS approach will help us traverse through all possible combinations of uppercase and lowercase transformations of the characters within the string. Here's the intuition breakdown for solving this problem:

Start from the first character: We begin the process with the first character of the string.
Recursive exploration: For each character, we have two choices (provided it's an alphabetical character and not a digit):
- Keep the current character as is and proceed to the next one.
- Change the current character's case (from lowercase to uppercase or vice versa) and move to the next one.
Base case: If we reach the end of the string (i.e., index i is equal to the string length), we've completed a permutation and it's added to the list of results.
Backtracking: After exploring one option (like keeping the character as is) for the current position, we backtrack to explore the other option (changing the case).
Result accumulation: As we hit the base case at different recursive call levels, we collect all permutations of the string.

This recursive approach works because it explores all possible combinations by trying each option at each step. The use of the bitwise XOR operation ^ 32 is a clever trick to toggle the case of an alphabetical character since converting between lowercase to uppercase (or vice versa) in ASCII entails flipping the 6th bit.

Learn more about Backtracking patterns.

Solution Approach

The provided solution uses a Depth-First Search (DFS) algorithm along with a recursive helper function named dfs. This function is defined within the scope of the letterCasePermutation method.

Here's a step-by-step walk-through of the solution code:

A new list t is created from the original string s which is going to hold the characters that we are currently exploring through DFS.
An empty list ans is initialized which will eventually contain all the possible permutations of the string.
The dfs function defined inside the letterCasePermutation takes a single argument i, which is the index of the character in t we are currently exploring.
In the body of the dfs function, the base case checks if the index i is greater than or equal to the length of s. If it is, it means we've constructed a valid permutation of string s in the list t and we append this permutation to ans.
If the base case condition is not met, we first call dfs(i + 1) without altering the current character. This recurses on the decision to keep the current character as is.
Next, if the current character is alphabetic (t[i].isalpha()), we toggle its case using t[i] = chr(ord(t[i]) ^ 32). The ord function gets the ASCII value of the character, ^ 32 toggles the 6th bit which changes the case, and chr converts the ASCII value back to the character. After changing the case, we call dfs(i + 1) again, exploring the decision tree path where the current character's case is toggled.
By recursively calling dfs with 'unchanged' and 'changed' states of each character, all combinations are eventually visited, and the resulting strings appended to ans.

The DFS here is a recursive pattern that explores each possibility and undoes (backtracks) that choice before exploring the next possibility. The data structure used is a basic Python list which conveniently allows us to both change individual elements in place and join them into strings when we need to add a permutation to the results.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example using the string "0a1".

We start by setting up an empty list ans that will store our final permutations and a list t from the string s, which is "0a1". List t will hold the characters that we are currently exploring through the DFS algorithm.
Since the first character '0' is not an alphabetical character, we only have one option for it; we keep it as is. So, we move on to the next character.
The next character is 'a'. Here, we have two choices:
- Keep 'a' as it is and proceed to the next character, which will be '1'. This sequence is "0a1". Since '1' is not alphabetical, we keep it as is and add "0a1" to ans.
- Toggle the case of 'a' to 'A' and then proceed to the next character, '1'. This sequence is "0A1". Again, we keep '1' as it is and add "0A1" to ans.
At this point, the dfs function has recursively explored and returned from both branches for character 'a', and the two permutations of the string are saved in ans, which now contains ["0a1", "0A1"].
Since there are no more characters to explore, the recursion terminates, and the ans list now holds all the possible permutations regarding the case of alphabetic characters.

And that's the end of the example. The original list "0a1" only had one alphabetical character that could be toggled, which resulted in two different string permutations: "0a1" and "0A1".

Solution Implementation

1class Solution:
2
3    def letterCasePermutation(self, s: str) -> List[str]:
4        # Helper function for depth-first search
5        def dfs(index):
6            # Base case: if the current index is equal to the length of the string
7            if index == len(s):
8                # Append the current permutation to the answer list
9                permutations.append(''.join(current_string))
10                return
11            # Recursive case: move to the next character without changing the case
12            dfs(index + 1)
13          
14            # If the current character is alphabetic, we can change its case
15            if current_string[index].isalpha():
16                # Flip the case: if the current character is uppercase, make it lowercase and vice versa
17                current_string[index] = chr(ord(current_string[index]) ^ 32)
18                # Continue the search with the flipped case character
19                dfs(index + 1)
20                # Revert the change for backtracking purposes
21                current_string[index] = chr(ord(current_string[index]) ^ 32)
22
23        # Convert the input string to a list, making it mutable
24        current_string = list(s)
25        # Initialize a list to store all possible permutations
26        permutations = []
27        # Start the depth-first search from the first character
28        dfs(0)
29        # Return the computed permutations
30        return permutations
31
32# Example of usage:
33# sol = Solution()
34# result = sol.letterCasePermutation("a1b2")
35# print(result)  # Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
36

1class Solution {
2    private List<String> permutations = new ArrayList<>(); // List to hold the string permutations
3    private char[] charArray; // Character array to facilitate permutation generation
4
5    // Public method to generate letter case permutations for a given string
6    public List<String> letterCasePermutation(String s) {
7        charArray = s.toCharArray(); // Convert string to character array for modification
8        generatePermutations(0); // Start recursion from the first character
9        return permutations; // Return all generated permutations
10    }
11
12    // Helper method to recursively generate permutations
13    private void generatePermutations(int index) {
14        // Base case: If the end of the array is reached, add the current permutation to the list
15        if (index >= charArray.length) {
16            permutations.add(new String(charArray));
17            return;
18        }
19        // Recursively call the method to handle the next character without modification
20        generatePermutations(index + 1);
21
22        // If the current character is alphabetic, toggle its case and proceed with recursion
23        if (Character.isLetter(charArray[index])) {
24            // Toggle the case: lowercase to uppercase or vice versa using XOR operation with the space character
25            charArray[index] ^= ' ';
26            generatePermutations(index + 1);
27          
28            // IMPORTANT: revert the character back to its original case after the recursive call
29            charArray[index] ^= ' '; // This step ensures the original structure is intact for future permutations
30        }
31        // If the character is not alphabet, it is left as-is and the recursion takes care of other characters
32    }
33}
34

1#include <vector>
2#include <string>
3#include <functional>
4
5class Solution {
6public:
7    // Function to generate all permutations of a string where each letter can be lowercase or uppercase
8    std::vector<std::string> letterCasePermutation(std::string str) {
9        // Resultant vector to store all permutations
10        std::vector<std::string> permutations;
11
12        // Utility lambda function to perform a Depth-First Search (DFS) for all possible letter case combinations
13        std::function<void(int)> dfs = [&](int index) {
14            // Base case: if we reach the end of the string, add the current permutation to the results
15            if (index >= str.size()) {
16                permutations.emplace_back(str);
17                return;
18            }
19
20            // Recursive case: continue with the next character without changing the current one
21            dfs(index + 1);
22
23            // Only if the current character is alphabetical (either uppercase or lowercase)
24            // we toggle its case and recursively continue
25            if (isalpha(str[index])) {
26                // Toggle the case of the current character: lowercase to uppercase or vice versa
27                // XOR with 32 takes advantage of the fact that the ASCII values of upper and lower case
28                // letters differ by exactly 32
29                str[index] ^= 32;
30
31                // Recursive call with the case of the current character toggled
32                dfs(index + 1);
33
34                // Optional: Toggle the case back if you want to use the original string elsewhere
35                // after this function call. If str is not used after this, you can omit this step.
36                // str[index] ^= 32;
37            }
38        };
39
40        // Start DFS from index 0
41        dfs(0);
42
43        // Return all generated permutations
44        return permutations;
45    }
46};
47

1// Function that generates all possible permutations of a string 
2// with letters toggled between uppercase and lowercase.
3// It uses Depth-First Search (DFS) to explore all variations.
4function letterCasePermutation(s: string): string[] {
5    const length = s.length;                 // The length of the input string
6    const charArray = [...s];                // Converts the string to an array of characters
7    const results: string[] = [];            // Stores the resulting permutations
8
9    // Helper function to perform DFS
10    const dfs = (index: number) => {
11        if (index === length) {               // If the end of the string is reached,
12            results.push(charArray.join('')); // join the characters to form a permutation and add to results.
13            return;
14        }
15        dfs(index + 1);                       // Recursive call with the next character (no change)
16
17        // Check if the current character is a letter and can change case
18        if (isLetter(charArray[index])) {
19            toggleCase(charArray, index);     // Toggle the case of the character at the current index
20            dfs(index + 1);                   // Recursive call with the toggled character
21        }
22    };
23
24    // Function to check if a character is a letter (could be replaced with regex or other methods)
25    function isLetter(c: string): boolean {
26        return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
27    }
28
29    // Function that toggles the case of a letter by using bitwise XOR with the space character (32)
30    function toggleCase(arr: string[], index: number): void {
31        arr[index] = String.fromCharCode(arr[index].charCodeAt(0) ^ 32);
32    }
33
34    dfs(0); // Start the DFS from the first character
35    return results; // Return the array of permutations
36}
37

Time and Space Complexity

The given Python code generates all possible permutations of a string s where the permutation can include lowercase and uppercase characters. A depth-first search (DFS) algorithm is employed to explore all possibilities.

Time Complexity:

To analyze the time complexity, let us consider the number of permutations possible for a string with n characters. Each character can either remain unchanged or change its case if it's an alphabetic character. For each alphabetic character, there are 2 possibilities (uppercase or lowercase), while non-alphabetic characters have only 1 possibility (as they don't have case). If we assume there are m alphabetic characters in the string, there would be 2^m different permutations.

The DFS function is recursively called twice for each alphabetic character (once without changing the case, once with the case changed), and it's called once for each non-alphabetic character. Thus, the time complexity of this process can be represented as:

O(2^m * n), where n is the length of the string and m is the number of alphabetic characters in the string as each permutation includes building a string of length n.

Space Complexity:

The space complexity includes the space needed for the recursion call stack as well as the space for storing all the permutations. The maximum depth of the recursive call stack would be n, as that’s the deepest the DFS would go. The space needed for ans will be O(2^m * n) as we store 2^m permutations, each of length n.

However, one might consider the space used for each layer of the recursion separately from the space used to store the results since the latter is part of the problem's output. If we only consider the space complexity for the recursion (excluding the space for the output), then the space complexity would be O(n).

Combining both the space for the recursion and the output, the space complexity can be represented as:

O(2^m * n + n), which simplifies to O(2^m * n) when considering 2^m to be significantly larger than n.

In conclusion, the time complexity is O(2^m * n) and the space complexity is O(2^m * n) when accounting for both the recursion stack and the output list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know