<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:
    def kSimilarity(self, s1: str, s2: str) -> int:
        # abc -> bca
        # cba -> bca
        # bca -> bca
        # naively: check position of "supposed to be", swap
        # can we greedily do this? what if there is 2 options?
        
        # abac -> baca
        # greedy: choose first a
        # baac -> baca
        # ba is good -> can leave it? yes
        # can we just leave all same positions? yes
        
        # if we can leave and do it greedily
        # k(s1,s2)-> leave all same -> swap first char if diff -> k(s1[1:],s2[1:])
        # it seems we can do greedily, if we leave all same at each point
        # checking for all same -> only one more will be same after that
        # no, we have to check between different alphabet
        
        # dp
        # dp[s1,s2] = if same: dp[s1[1:],s2[1:]]
        # dp[a,s2] for a is s1 after we swap first char to all possible position
        # s2 stays the same, don't need it
        
        @cache
        def dp(a):
            if len(a) == 0:
                return 0
            
            i = len(s1)-len(a)
            
            if a[0] == s2[i]:
                return dp(a[1:])
            
            result = float(inf)
            target = s2[i]
            for index in range(len(a)):
                if a[index] == target:
                    newA = list(a)
                    newA[0] = a[index]
                    newA[index] = a[0]
                    result = min(result, 1 + dp("".join(newA)[1:]))
                
            return result
        
        return dp(s1)
            
            
32299