<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 {
    string str_;
    string_view target_;

    // Input: from � start index in str_ moving from left to right
    // Output: the smallest k for which str_ and target_ are k-similar
    int backtrack(int from) {
        // The idea here is to find the first character in str_ not matching
        // the respective character in target_ and find the best way
        // to swap it with some character to the right resulting in the smallest k
    
        // 0. Skip first matching characters 
        while (from != str_.size() && str_[from] == target_[from])
            ++from;
        
        if (from == str_.size())
            return 0;

        // 1. Try to find the best swap which gives us two matching characters
        //
        //    Example:    s2 = acba
        //                s1 = baac
        //    best swap:       ^ ^
        //    instead of:      ^^
        for (int to = from + 1; to != str_.size(); ++to) {
            if (str_[to] != target_[from] || str_[from] != target_[to])
                continue;

            // All best swaps candidates are equivalent because they yield the smallest k:
            // str_[to] gets swapped with character matching target_[to] and
            // thus will be skipped on next steps and won't increase the resulting k

            swap(str_[from], str_[to]);
            int result = 1 + backtrack(from + 1);
            swap(str_[from], str_[to]);
    
            // Pick the first best swap candidate
            return result;
        }

        // 2. If no best swap found, find swap which yields smallest k among every possible swap
        int result = INT_MAX;

        for (int to = from + 1; to != str_.size(); ++to) {
            // Don't swap with characters that already match target_[to] to avoid increasing of k
            if (str_[to] != target_[from] || str_[to] == target_[to])
                continue;
            
            // Remaining swap candidates only gives us +1 matching character: str_[from]
            // There's no better way to find the smallest k other than recursing in each possible suffix

            swap(str_[from], str_[to]);
            result = min(result, 1 + backtrack(from + 1));
            swap(str_[from], str_[to]);
        }
    
        return result;
    }

public:
    int kSimilarity(string& s1, string_view s2) {
        str_ = move(s1);
        target_ = s2;
        return backtrack(0);
    }
};
8680