LeetCode 784: Letter Case Permutation Solution

Master LeetCode problem 784 (Letter Case Permutation), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

784. Letter Case Permutation

Medium

String Backtracking Bit Manipulation

Problem Explanation

Explanation

To solve this problem, we can use backtracking. We iterate through each character in the input string. For each character, we have two choices: either convert it to lowercase or convert it to uppercase. We recursively explore both choices for each character, building up the possible permutations. We keep track of the current state of the string being built and when we reach the end of the input string, we add the current state to the result list.

Algorithm

Initialize an empty list to store the result.
Define a helper function that takes the input string, current index, and current state of the string being built.
In the helper function, if the current index is equal to the length of the input string, add the current state to the result list and return.
If the current character is a digit, keep it unchanged and recursively call the helper function for the next index.
If the current character is a letter, recursively call the helper function twice: once with the current character converted to lowercase and once with it converted to uppercase.
Return the result list after exploring all permutations.

Time Complexity

The time complexity of this algorithm is O(2^n) where n is the length of the input string. This is because for each character in the input string, we have two choices: convert it to lowercase or uppercase.

Space Complexity

The space complexity is also O(2^n) due to the recursion stack and the space needed to store the resulting permutations.

Solution Code

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<>();
        backtrack(result, s, 0, new StringBuilder());
        return result;
    }
    
    private void backtrack(List<String> result, String s, int index, StringBuilder current) {
        if (index == s.length()) {
            result.add(current.toString());
            return;
        }
        
        char ch = s.charAt(index);
        if (Character.isDigit(ch)) {
            current.append(ch);
            backtrack(result, s, index + 1, current);
            current.deleteCharAt(current.length() - 1);
        } else {
            current.append(Character.toLowerCase(ch));
            backtrack(result, s, index + 1, current);
            current.deleteCharAt(current.length() - 1);
            
            current.append(Character.toUpperCase(ch));
            backtrack(result, s, index + 1, current);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 784 (Letter Case Permutation)?

This page provides optimized solutions for LeetCode problem 784 (Letter Case Permutation) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 784 (Letter Case Permutation)?

The time complexity for LeetCode 784 (Letter Case Permutation) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 784 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 784 in Java, C++, or Python.

Back to LeetCode Solutions