<p>Strings <code>s1</code> and <code>s2</code> are <code>k</code><strong>-similar</strong> (for some non-negative integer <code>k</code>) if we can swap the positions of two letters in <code>s1</code> exactly <code>k</code> times so that the resulting string equals <code>s2</code>.</p>

<p>Given two anagrams <code>s1</code> and <code>s2</code>, return the smallest <code>k</code> for which <code>s1</code> and <code>s2</code> are <code>k</code><strong>-similar</strong>.</p>

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

<pre>
<strong>Input:</strong> s1 = &quot;ab&quot;, s2 = &quot;ba&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> The two string are 1-similar because we can use one swap to change s1 to s2: &quot;ab&quot; --&gt; &quot;ba&quot;.
</pre>

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

<pre>
<strong>Input:</strong> s1 = &quot;abc&quot;, s2 = &quot;bca&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The two strings are 2-similar because we can use two swaps to change s1 to s2: &quot;abc&quot; --&gt; &quot;bac&quot; --&gt; &quot;bca&quot;.
</pre>

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

<ul>
	<li><code>1 &lt;= s1.length &lt;= 20</code></li>
	<li><code>s2.length == s1.length</code></li>
	<li><code>s1</code> and <code>s2</code> contain only lowercase letters from the set <code>{&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;, &#39;f&#39;}</code>.</li>
	<li><code>s2</code> is an anagram of <code>s1</code>.</li>
</ul>

class Solution(object):
    def kSimilarity(self, s1, s2):
        
        def get_neighbors(n):
            #same_like_s2 = [n[i] == s2[i] for i in range(n)]
            #needed_by_s2 = []
            neighbors_1 = []
            neighbors_2 = []
            for i, c1 in enumerate(n):
                if n[i] != s2[i]:
                    break
            for j, c2 in enumerate(s2):
                if j < i:
                    continue
                if c1 == c2 and c1 != s2[i]:
                    # check, if double improvement
                    double_improvement = s2[i] == n[j]
                    char_list = list(n)  
                    # Swap characters at index 2 and index 6  
                    char_list[i], char_list[j] = char_list[j], char_list[i]  
                    if double_improvement:
                        neighbors_2.append(char_list)
                    else:
                        neighbors_1.append(char_list)
            return neighbors_2, neighbors_1

        # remove similarities:
        letter_num = {"a": 0,"b": 1,"c": 2,"d": 3,"e": 4,"f": 5}
        s1_new = []
        s2_new = []
        for k in range(len(s1)):
            if s1[k] != s2[k]:
                s1_new.append(letter_num[s1[k]])
                s2_new.append(letter_num[s2[k]])
        s1 = s1_new
        s2 = s2_new
        if s1 == s2:
            return 0
        stack_vec = [[] for _ in range(len(s1))] # an der i-ten stelle sind gemachte 1er moves
        stack_vec[0] = [(s1, 0)]
        while True:
            for i, a in enumerate(stack_vec):
                if a:
                    n, k = a.pop()
                    break
            if n == s2:
                return k
            neighbors_2, neighbors_1 = get_neighbors(n)
            stack_vec[i + 1] += [(n, k+1) for n in neighbors_1]
            stack_vec[i] += [(n, k+1) for n in neighbors_2]
20100