<p>Given a string <code>s</code>, you&nbsp;can transform every letter individually to be lowercase or uppercase to create another string.</p>

<p>Return <em>a list of all possible strings we could create</em>. Return the output in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;a1b2&quot;
<strong>Output:</strong> [&quot;a1b2&quot;,&quot;a1B2&quot;,&quot;A1b2&quot;,&quot;A1B2&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;3z4&quot;
<strong>Output:</strong> [&quot;3z4&quot;,&quot;3Z4&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 12</code></li>
	<li><code>s</code> consists of lowercase English letters, uppercase English letters, and digits.</li>
</ul>

from collections import defaultdict
class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        d1=defaultdict(int)
        l=[""]
        q=[-1]
        c=0
        while l:
            node=l.pop(0)
            ind=q.pop(0)
            for i in range(ind+1,len(s)):
                if(s[i].isalpha()):
                    if(d1[node+s[i].lower()]==0):
                        d1[node+s[i].lower()]=1
                    if(d1[node+s[i].upper()]==0):
                        d1[node+s[i].upper()]=1
                    l.append(node+s[i].lower())
                    q.append(i)
                    l.append(node+s[i].upper())
                    q.append(i)
                    break
                else:
                    if(d1[node+s[i]]==0):
                        d1[node+s[i]]=1
                        l.append(node+s[i])
                        q.append(i)
                        break
        for i in d1:
            c=max(c,len(i))
        fin=[]
        for i in d1:
            if(len(i)==c):
                fin.append(i)
        return fin
17600