from collections import deque
class Solution:
  def findLetterCaseStringPermutations(self, str):
    permutations = []
    # TODO: Write your code here
    #[a,b,c]
    #[a][A]
    #[ab][aB][Ab][AB]
    #[abc][abC][aBc][aBC][Abc][AbC][ABc][ABC]
    # so loop through string, if char is number just append to all queue items
    # for char is number, append it with 2 cases: lowercase and uppercase
    curr_queue = deque()
    curr_queue.append("")
    for character in str:
      curr_queue_length = len(curr_queue)
      for _ in range(curr_queue_length):
        curr_str = curr_queue.popleft()
        if character.isdigit():
          curr_str += character
          if(len(curr_str) >= len(str)):
            permutations.append(curr_str)
          else:
            curr_queue.append(curr_str)
        else: # is character need 2 cases lower and upper case
          if character.islower():
            lowercase = curr_str + character
            uppercase = curr_str + character.upper()
          else:
            lowercase = curr_str + character.lower()
            uppercase = curr_str + character
          if (len(lowercase) >= len(str)):
            permutations.append(lowercase)
            permutations.append(uppercase)
          else:
            curr_queue.append(lowercase)
            curr_queue.append(uppercase)
    return permutations