class Solution:
def __init__(self):
self.cache = {}
def kSimilarity(self, A: str, B: str) -> int:
if A + B in self.cache:
return self.cache[A + B]
if A == B:
return 0
for i in range(len(A)):
if A[i] != B[i]:
start = i
break
ans = len(A)
for i in range(start + 1, len(A)):
if B[i] == A[start] and A[i] != A[start]:
tmp = B[:start] + B[i] + B[start + 1:i] + B[start] + B[i + 1:]
ans = min(ans, self.kSimilarity(A, tmp) + 1)
self.cache[A + B] = ans
return ans