Problem statement

https://binarysearch.com/problems/Anagram-Difference/

Solution

Problem constraints allow us to use bruteforce with backtracking. The idea is to find element in a[x] equal to b[i] and swap elements in a.

Complexity

I think it is between O(2^n) and O(n!) for time and O(n) for space.

Code

class Solution:
    def solve(self, a, b):
        def dfs(a, b, i):
            n = len(a)
            if i == n: return 0
            if a[i] == b[i]: return dfs(a, b, i + 1)

            ans = n
            for x in range(i, n):
                if a[x] == b[i]:
                    a[i], a[x] = a[x], a[i]
                    ans = min(ans, 1 + dfs(a, b, i + 1))
                    a[i], a[x] = a[x], a[i]
            return ans

        return dfs(list(a), list(b), 0)