Letter Case Permutation

excerpt: Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. tags: permutation recursion backtracking exhaustive-enumeration

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create. You can return the output in any order.

Example 1:
Input: S = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:
Input: S = "3z4"
Output: ["3z4","3Z4"]

Example 3:
Input: S = "12345"
Output: ["12345"]

Example 4:
Input: S = "0"
Output: ["0"]

Constraints

  • S will be a string with length between 1 and 12.
  • S will consist only of letters or digits.

Problem Solving Process

Analyze the Problem

Define the Interface

Input: String s
Output: Array of strings

Classify the problem

  • Is this similar to a problem you have already seen before? Permutation.
  • Exhaustive Enumeration (Clue: All possible strings)
  • Order does not matter

The string s consists of letter or digits and the length is between 1 and 12. If the input consists only of numbers, just return it. We will have multiple permutation strings only if letters and digits or letters are given as the input string. Only if you see a letter then you process it, otherwise we append it to the result.

Work with Small Examples

n = 1

‘a’

‘a’, ‘A’

n = 2

“ab”

‘a’, ‘A’

‘ab’, ‘Ab’, ‘aB’, ‘AB’

n = 3

‘abc’

‘abc’, ‘Abc’, ‘aBc’, ‘ABc’, ‘abC’, ‘AbC’, ‘aBC’, ‘ABC’

outer loop 0 to length of the input inner loop

How to Implement?

  1. Solution will be very similar to the permutation problem
  2. We cannot change the index, we only need to either uppercase or lowercase. Processing consists of two choices, upper/lower.
  3. What approach can we use to solve this problem?
    • Recursion
    • Iteration
  4. Recursive Approach
    • Backtracking
    • We need to keep track of the index
    • Why does the index need to be kept track of?
    • So that we know which letter needs to transformed to upper or lower case
    • Base Case
      • If the current index = length of the given string
      • Append the permutation string to the output array
    • Unit of Work Process one letter or one digit If it is letter => uppercase/lowercase If it is a digit. => append it to the output
    • Do we do this unit of work before the recursive call or after the recursive call?
    • Before the recursive call
    • Do we want to return a value or is it returning void?
    • Build a partial solution that will eventually become a permutation
    • Do we pass it in as a parameter to the function?
    • How do we keep track of the output?
      • parameter of the function
    • Define a wrapper/helper function
    • How many recursive calls?
      • Two recursive calls for letters Two choices: upper/lower
      • One recursive call for digits

Time and Space Complexity

Time: O(2^nn) Space: O(2^nn)

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# @param {String} s
# @return {String[]}
def numeric?(s)
  begin
    Integer(s)
  rescue ArgumentError
    return false
  end  
  true
end

def wrapper(output, index, characters) 
  if index == characters.size
    output << characters.join
  else
    # choices: lowercase, uppercase
    letter = characters[index]
    if numeric?(letter)
      wrapper(output, index+1, characters)
    else
      lower = letter.downcase
      characters[index] = lower

      wrapper(output, index+1, characters)

      upper = letter.upcase
      characters[index] = upper
      
      wrapper(output, index+1, characters)
    end
  end
end

def letter_case_permutation(s)
  output = []
  index = 0
  characters = s.chars
  wrapper(output, index, characters)
  output
end

The problem requires us to find all the possible strings by changing the case of the letters in the given string s. Here’s a step-by-step guide to solve this problem:

  1. Initialize the Result: Create a list to hold the results.
  2. Iterate through the String: Go through each character in the given string s.
  3. Handle Letters and Digits Differently: If the current character is a letter, both lower and upper cases are possible. If it’s a digit, there’s only one possibility.
  4. Use Recursion or Iteration: You can either use recursion to build the strings character by character or use an iterative approach to handle the permutations.
  5. Return the Result: Finally, return the list containing all the permutations.

Here’s a solution using an iterative approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        results = [""]

        for char in s:
            if char.isalpha():
                results = [prefix + ch for prefix in results for ch in [char.lower(), char.upper()]]
            else:
                results = [prefix + char for prefix in results]

        return results

Explanation:

  • For each character in s, if it’s a letter, we add both the lower and upper cases to the current results.
  • If it’s a digit, we simply add it to the current results.
  • We use list comprehension to create the new results at each step.

Analyze the Problem

  1. Define the Interface Input: String s Output: Array of strings

  2. Classify the problem Is this similar to a problem you have already seen before? Permutation

  3. Exhaustive Enumeration (Clue: All possible strings)

  4. Order does not matter

  5. s consists of letter or digits and the length is between 1 and 12

  6. If the input consists only of numbers, just return it. We will have multiple permutation strings only if letters and digits or letters are given as the input string.

  7. Only if you see a letter then you process it, otherwise we append it to the result.

How to Implement?

  1. Solution will be very similar to the permutation problem

  2. We cannot change the index, we only need to either uppercase or lowercase Processing: Two choices, uppper/lower

  3. What approach can we use to solve this problem? Recursion Iteration

  4. Recursive Approach

    • Backtracking
    • We need to keep track of the index
    • Why index needs to be kept track of?
    • So that we know which letter needs to transformed to upper or lower case
    • Base Case
      • If the current index = length of the given string
      • Append the permutation string to the output array
    • Unit of Work Process one letter or one digit If it is letter => uppercase/lowercase If it is digit. => append it to the output
    • Do we do this unit of work before the recursive call or after the recursive call?
    • Before the recursive call
    • Do we want to return a value or is it returning void?
    • Build a partial solution that will eventually become a permutation
    • Do we pass it in as a parameter to the function?
    • How do we keep track of the output?
      • parameter of the function
    • Define a wrapper/helper function
    • How many recursive calls?
      • Two recursive calls for letters Two choices: upper/lower
      • One recursive call for digits
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def numeric?(s)
  begin
     Integer(s)
  rescue ArgumentError
      return false
  end
     true
end

def wrapper(output, index, characters)
    if index == characters.size
        output << characters.join
    else
       letter = characters[index]
       if numeric?(letter)
          wrapper(output, index+1, characters) 
       else
          lower = letter.downcase
           characters[index] = lower
           wrapper(output, index+1, characters)

           upper = letter.upcase
           characters[index] = upper

           wrapper(output, index+1, characters)
       end
    end     
end

# @param {String} s
# @return {String[]}
def letter_case_permutation(s)
    output = []
    index = 0
    characters = s.chars
    wrapper(output, index, characters)
    output
end