Scale Engineer

Letter Case Permutation

Med
#0738Time: 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: 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.1 company
Patterns
BacktrackingBit Manipulation
Data structures
String
Companies
Yelp

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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":

  1. Start with permutations = [""].
  2. Process 'a': permutations becomes ["a", "A"].
  3. Process '1': permutations becomes ["a1", "A1"].
  4. 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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem