Letter Case Permutation

MEDIUM

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.

Example 1:

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

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

Constraints:

1 <= s.length <= 12
s consists of lowercase English letters, uppercase English letters, and digits.

Approaches

Checkout 3 different approaches to solve Letter Case Permutation. Click on different approaches to view the approach and algorithm in detail.

Iterative Approach (BFS)

This approach iteratively builds the list of all possible permutations. It starts with a list containing just an empty string. Then, for each character in the input string, it expands the list of permutations. If the character is a letter, it doubles the size of the list by creating two new versions for each existing permutation (one with the lowercase letter, one with the uppercase). If it's a digit, it simply appends the digit to every existing permutation.

Algorithm

Initialize a list of strings, permutations, and add an empty string to it.
Iterate through each character c of the input string s.
For each character, create a temporary list newPermutations.
Iterate through each string p currently in the permutations list.
If c is a letter, add two new strings to newPermutations: p with the lowercase of c appended, and p with the uppercase of c appended.
If c is a digit, add one new string to newPermutations: p with c appended.
After processing all strings for the current character, replace permutations with newPermutations.
After iterating through all characters of s, the permutations list holds the final result.

This method can be visualized as a Breadth-First Search (BFS) through the decision tree of possibilities. We maintain a list of all permutations generated so far. We process the input string character by character, and at each step i, we use the permutations of length i to generate all permutations of length i+1.

For example, with s = "a1b":

Start with permutations = [""].
Process 'a': permutations becomes ["a", "A"].
Process '1': permutations becomes ["a1", "A1"].
Process 'b': permutations becomes ["a1b", "a1B", "A1b", "A1B"].

While conceptually simple, this implementation creates a new list and new strings at each step, which can be inefficient.

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> permutations = new ArrayList<>();
        if (s == null) {
            return permutations;
        }
        permutations.add("");

        for (char c : s.toCharArray()) {
            List<String> newPermutations = new ArrayList<>();
            for (String p : permutations) {
                if (Character.isLetter(c)) {
                    newPermutations.add(p + Character.toLowerCase(c));
                    newPermutations.add(p + Character.toUpperCase(c));
                } else {
                    newPermutations.add(p + c);
                }
            }
            permutations = newPermutations;
        }
        return permutations;
    }
}

Complexity Analysis

Time Complexity: O(N * 2^L), where N is the length of the string and L is the number of letters. For each of the `N` characters, we iterate through the current list of permutations and create new strings. The total number of generated strings is proportional to `N * 2^L`.Space Complexity: O(N * 2^L), where N is the length of the string and L is the number of letters. This is dominated by the space required to store the `2^L` output strings of length `N`. The intermediate list `newPermutations` also contributes to this.

Pros and Cons

Pros:

It's an iterative approach, so it avoids recursion and the risk of stack overflow.
The logic is straightforward and easy to follow.

Cons:

Creating a new list (newPermutations) in each iteration can lead to significant memory allocation and garbage collection overhead.
String concatenation in a loop (p + c) creates many intermediate string objects, which is inefficient.

Code Solutions

Checking out 3 solutions in different languages for Letter Case Permutation. Click on different languages to view the code.

class Solution { private List < String > ans = new ArrayList <>(); private char [] t ; public List < String > letterCasePermutation ( String s ) { t = s . toCharArray (); dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= t . length ) { ans . add ( String . valueOf ( t )); return ; } dfs ( i + 1 ); if ( t [ i ] >= 'A' ) { t [ i ] ^= 32 ; dfs ( i + 1 ); } } }

Video Solution

Watch the video walkthrough for Letter Case Permutation

Patterns:

BacktrackingBit Manipulation

Data Structures:

String

Companies:

Yelp |