<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>

# time limit exceeded
# on test case 23 out of 66
# s1 = "fffeaacbdbdafcfbbafb"
# s2 = "abcbdfafffefabdbbafc"
# on testcase 64 out of 66
# s1 = "baabaaabaabbbbbbbaba"
# s2 = "abbabbbabbabaaababab"
# BFS
class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        q = deque()
        q.append((0, [c for c in s1], 0))
        min_swaps = len(s2)
        while q:
            q_size = len(q)
            for _ in range(q_size):
                swaps, cur_list, cur_i = q.popleft()
                if cur_i == len(s2):
                    min_swaps = min(min_swaps, swaps)
                    continue

                if cur_list[cur_i] != s2[cur_i]:
                    for i in range(cur_i + 1, len(cur_list)):
                        if cur_list[i] == s2[cur_i] and cur_list[i] != s2[i]:
                            new_list = cur_list[::]
                            new_list[cur_i], new_list[i] = new_list[i], new_list[cur_i]
                            q.append((swaps + 1, new_list, cur_i + 1))
                else:
                    q.append((swaps, cur_list, cur_i + 1))

        return min_swaps

# BFS
class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        c_to_list_i = defaultdict(list)
        for ind, val in enumerate(s1):
            if val not in c_to_list_i:
                c_to_list_i[val] = []
            c_to_list_i[val].append(ind)

        cnt = 0
        queue = deque([s2])
        visit = {s2}
        while queue:
            l = len(queue)
            for i in range(l):
                possible = queue.popleft()
                if possible == s1:
                    return cnt
                lst = list(possible)
                for i in range(len(lst)):
                    if lst[i] != s1[i]:
                        for ind in c_to_list_i[lst[i]]:
                            if lst[ind] == s1[ind]:
                                continue
                            lst[i], lst[ind] = lst[ind], lst[i]
                            s = "".join(lst)
                            if s not in visit:
                                visit.add(s)
                                queue.append(s)
                            lst[ind], lst[i] = lst[i], lst[ind]
                        break
            cnt += 1
        return None



# BFS
class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        def nei(x):
            i = 0
            while x[i] == s2[i]:
                i = i + 1

            neigh_list = []
            for j in range(i + 1, len(x)):
                if x[j] == s2[i]:
                    neigh_list.append(x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])

            return neigh_list

        q  = [(s1, 0)]
        # need the seen set to not time limit exceed
        seen = {s1}
        for x, d in q:
            if x == s2:
                return d
            for y in nei(x):
                if y not in seen:
                    seen.add(y)
                    q.append((y, d + 1))


# example of when to do a perfect swap
# s1 = abcdfe
# s2 = fbcdae
# example of when to do a regular swap
# s1 = abc -> send bc to helper
# s2 = bca -> swap to make acb but send cb to helper
# DFS
# from functools import cache
# class Solution:
#     def kSimilarity(self, s1: str, s2: str) -> int:
#         @cache
#         def helper(s1, s2):
#             if len(s1) == 0:
#                 return 0
#             if s1 == s2:
#                 return 0
#             if s1[0] == s2[0]:
#                 return helper(s1[1:], s2[1:])
#             for i in range(1, len(s2)):
#                 # perfect swap
#                 if s1[0] == s2[i] and s2[0] == s1[i]:
#                     return 1 + helper(s1[1: i] + s1[i + 1:], s2[1: i] + s2[i + 1:])

#             ans = 20
#             for i in range(1, len(s2)):
#                 if s1[0] == s2[i]:
#                     ans = min(ans, 1 + helper(s1[1:], s2[1: i] + s2[0] + s2[i + 1:]))

#             return ans

#         return helper(s1, s2)

26600