Binary Permutation

Return all the permutations of a string, matching the sequence but only changing case.

For example:

input:
'abc'

output:
['abc', 'abC', 'aBc', 'aBC', 'Abc', 'AbC', 'ABc', 'ABC']

The Idea: Begin from the base case (empty string), and branch out two different ways (capital and lowercase) to the parent string.

Complexity: O(2^n) time and space

import queue

def binary_permutation(str):
    if not str:
        return []

    q = queue.Queue()
    q.put(('', -1))
    sol = []

    while not q.empty():
        cur_str, i = q.get()
        if i < len(str) - 1:
            q.put((cur_str + str[i+1], i + 1))
            q.put((cur_str + str[i+1].upper(), i + 1))
        else:
            sol.append(cur_str)
            while not q.empty():
                sol.append(q.get()[0])
            return sol


print(binary_permutation('abc'))
print(binary_permutation('fidfj'))
print(binary_permutation('ok'))
print(binary_permutation('l'))