854. K-Similar Strings

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.

class Solution {
    unordered_map<string, int> dp;
public:
    int kSimilarity(string A, string B) {
        if(dp.count(A)) return dp[A];
        int& res = dp[A] = INT_MAX;
        for(int i = 0; i < A.length(); i++) {
            if(A[i] == B[i]) continue;
            vector<int> match;
            for(int j = i + 1; j < A.length(); j++) {
                if(B[i] != A[j]) continue;
                match.push_back(j);
                if(B[j] == A[i]) {
                    swap(A[i], A[j]);
                    return res = 1 + kSimilarity(A.substr(i + 1), B.substr(i + 1));
                }
            }
            
            for(auto& j : match) {
                swap(A[i], A[j]);
                res = min(res, 1 + kSimilarity(A.substr(i + 1), B.substr(i + 1)));
                swap(A[i], A[j]);
            }
            
            return res; 
        }
        return res = 0;
    }
};