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

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

&nbsp;
Example 1:

Input: s1 = "ab", s2 = "ba"
Output: 1


Example 2:

Input: s1 = "abc", s2 = "bca"
Output: 2


&nbsp;
Constraints:


	1 &lt;= s1.length &lt;= 20
	s2.length == s1.length
	s1 and s2 contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}.
	s2 is an anagram of s1.


class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        n = len(s1)
        
        def helper(i, curr, dp):
            if curr == s2:
                return 0
            
            if curr not in dp[i]:
                if curr[i] == s2[i]:
                    dp[i][curr] = helper(i+1, curr, dp)
                else:
                    temp = sys.maxsize
                    for j in range(i+1, n):
                        if curr[j] == s2[i]:
                            temp = min(temp, 1+helper(i+1, curr[:i]+curr[j]+curr[i+1:j]+curr[i]+curr[j+1:], dp))

                    dp[i][curr] = temp
            return dp[i][curr]
        
        dp = [{} for _ in range(n)]
        return helper(0, s1, dp)
class Solution {
    public int kSimilarity(String s1, String s2) {
        HashSet<String> vis = new HashSet<>();
        
        ArrayDeque<String> queue = new ArrayDeque<>();
        int level = 0;
        queue.add(s1);
        
        while(queue.size() > 0){
            int size = queue.size();
            for(int i=0;i<size;i++){
                
                String rem = queue.remove();        // remove
                
                if(vis.contains(rem)){              // Mark*
                    continue;
                }
                vis.add(rem);
                
                if(rem.equals(s2)){                 // Work
                    return level;
                }
                
                // Add
                for(String s : getNeighbors(rem,s2)){
                    if(!vis.contains(s)){
                        queue.add(s);
                    }
                }
            }
            level++;
        }
        return -1;
    }
    
    public ArrayList<String> getNeighbors(String rem,String s2){
        ArrayList<String> res = new ArrayList<>();
        
        int idx = -1;
        for(int i=0;i<rem.length();i++){
            if(rem.charAt(i) != s2.charAt(i)){
                idx = i;
                break;
            }
        }
        
        for(int j=idx+1;j<rem.length();j++){
            if(rem.charAt(j) == s2.charAt(idx)){
                String s = swap(rem,idx,j);
                res.add(s);
            }
        }
        
        return res;
    }
    
    public String swap(String str,int i,int j){
        StringBuilder sb = new StringBuilder(str);
        char chi = sb.charAt(i);
        char chj = sb.charAt(j);
        
        sb.setCharAt(i,chj);
        sb.setCharAt(j,chi);
        
        return sb.toString();
    }
}
class Solution {
public:
    unordered_map<string,int>m;
    int solve(string &s1,string &s2,int i)
    {
        if(i==s1.length())
            return 0;
        if(m.find(s1)!=m.end())return m[s1];
        if(s1[i]==s2[i])
            return m[s1]=solve(s1,s2,i+1);
        int ans=1e5;
        for(int j=i+1;j<s1.length();j++)
        {
            if(s1[j]==s2[i])
            {
                swap(s1[j],s1[i]);
                ans=min(ans,1+solve(s1,s2,i+1));
                swap(s1[j],s1[i]);
            }
        }
        return m[s1]=ans;
    }
    int kSimilarity(string s1, string s2) {
        return solve(s1,s2,0);
    }
};
var kSimilarity = function(s1, s2) {
    // abc --> bca
    // swap from 0: a !== b, find next b, swap(0,1) --> bac
    // swap from 1: a !== c, find next c, swap(1,2) --> bca
    return bfs(s1, s2);    
};

const bfs = (a,b)=>{
    if(a===b)
        return 0;
    const visited = new Set();
    const queue = [];
    queue.push([a,0,0]); // str, idx, swapCount
    while(queue.length>0)
    {
        let [s, idx, cnt] = queue.shift();
        while(s[idx]===b[idx])
        {
                idx++;
        }
        for(let j = idx+1; j<s.length; j++)
        {
            if(s[j]===b[idx]) {
                s = swap(s, idx, j);
                
                if(s===b) {
                    return cnt+1;
                }
            
                if(!visited.has(s))
                {
                    queue.push([s.slice(), idx, cnt+1]);
                    visited.add(s.slice());
                }
                
                // swap back for later index
                s = swap(s, idx, j);
            }
        }
    }
    return -1;
}

const swap = (s, i, j)=>{
  let arr = s.split('');
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
  return arr.join('');
}
K-Similar Strings