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

Given two anagrams A and B, return the smallest K for which A and B are K-similar.

Example 1:

Input: A = "ab", B = "ba"
Output: 1


Example 2:

Input: A = "abc", B = "bca"
Output: 2


Example 3:

Input: A = "abac", B = "baca"
Output: 2


Example 4:

Input: A = "aabc", B = "abca"
Output: 2

Note:

1. 1 <= A.length == B.length <= 20
2. A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

## Solution

#### Approach Framework

Explanation

We’ll call the underlying graph of the problem, the graph with 6 nodes 'a', 'b', ..., 'f' and the edges A[i] -> B[i]. Our goal is for this graph to have only self-edges (edges of the form a -> a.) Let’s make some deductions about how swaps between A[i] and A[j] affect this graph, and the nature of optimal swap schedules.

If A = 'ca...' and B = 'ab...', then the first two edges of the underlying graph are c -> a and a -> b; and a swap between A[1] and A[0] changes these two edges to the single edge c -> b. Let’s call this type of operation ‘cutting corners’. Intuitively, our optimal swap schedule always increases the number of matches (A[i] == B[i]s) for each swap, so cutting corners is the only type of operation we need to consider. (This is essentially the happy swap assumption, proved in 765 – Couples Holding Hands)

Now consider any cycle decomposition of the underlying graph. [This decomposition (or the number of cycles), is not necessarily unique.] Through operations of cutting corners, we’ll delete all the (non-self) edges. Each cycle of length k requires k-1 operations to delete. Thus, the answer is just the minimum possible value of \sum (C_k – 1)∑(Ck​−1), where C_1, \cdots C_kC1​,⋯Ck​ are the lengths of the cycles in some cycle decomposition of the underlying graph. This can be re-written as \text{(Number of non-self edges)} – \text{(Number of cycles)}(Number of non-self edges)−(Number of cycles). Hence, we want to maximize the number of cycles in a cycle decomposition of the underlying graph.

#### Approach 1: Brute Force with Dynamic Programming

Intuition and Algorithm

Let ⋯ be possible cycles of the underlying graph . Let’s attempt to write ​ for some constants ​. Then, the number of cycles is .

We can represent  and ​ as the number of directed edges from node  to . For example, if ​ is the cycle a -> b -> d -> e -> a, then ​ is a -> b plus b -> d plus d -> e plus e -> a. This can be represented as a column vector possibles[0] of 1s and 0s, with four 1s, (each possibles[0][i] == 1 represents the ith directed edge being there [and having quantity 1]). Similarly, the graph  can also be represented as a column vector.

This sets the stage for dynamic programming. For each graph , represented as a column vector, say we want to find numCycles(G). We can take all possible cycles , and check if  contains . If it does, then a candidate answer is 1 + numCycles(G - C).

It should also be noted that maximizing the number of cycles cannot be done in a greedy way, i.e. by always removing the lowest size cycle. For example, consider the graph with edges a -> b -> c -> ab -> d -> e -> b, and c -> e -> f -> c. Those form cycles, and there is a fourth 3-cycle b -> c -> e -> b. If we remove that cycle first, then we would have only two cycles; but if we remove the first 3 cycles, then we would have three cycles.

Complexity Analysis

• Time Complexity: , where  is the length of the string, and  is the length of the alphabet.
• Space Complexity: .
class Solution {
String[] alphabet = new String[]{"a", "b", "c", "d", "e", "f"};
Map<String, Integer> memo;

public int kSimilarity(String A, String B) {
if (A.equals(B)) return 0;
int N = A.length();
memo = new HashMap();
int ans = 0;

int[] count = new int[alphabet.length * alphabet.length];
for (int i = 0; i < N; ++i)
if (A.charAt(i) != B.charAt(i)) {
count[alphabet.length * (A.charAt(i) - 'a') + (B.charAt(i) - 'a')]++;
ans++;
}

List<int[]> possibles = new ArrayList();
// Enumerate over every cycle
for (int size = 2; size <= alphabet.length; ++size)
search: for (String cycle: permutations(alphabet, 0, size)) {
// Check if cycle is canonical
for (int i = 1; i < size; ++i)
if (cycle.charAt(i) < cycle.charAt(0))
continue search;

int[] row = new int[count.length];
for (int i = 0; i < size; ++i) {
int u = cycle.charAt(i) - 'a';
int v = cycle.charAt((i+1) % size) - 'a';
row[alphabet.length * u + v]++;
}
}

int[] ZERO = new int[count.length];
memo.put(Arrays.toString(ZERO), 0);
return ans - numCycles(possibles, count);
}

public int numCycles(List<int[]> possibles, int[] count) {
String countS = Arrays.toString(count);
if (memo.containsKey(countS)) return memo.get(countS);

int ans = Integer.MIN_VALUE;
search: for (int[] row: possibles) {
int[] count2 = count.clone();
for (int i = 0; i < row.length; ++i) {
if (count2[i] >= row[i])
count2[i] -= row[i];
else
continue search;
}
ans = Math.max(ans, 1 + numCycles(possibles, count2));
}

memo.put(countS, ans);
return ans;
}

public List<String> permutations(String[] alphabet, int used, int size) {
List<String> ans = new ArrayList();
if (size == 0) {
return ans;
}

for (int b = 0; b < alphabet.length; ++b)
if (((used >> b) & 1) == 0)
for (String rest: permutations(alphabet, used | (1 << b), size - 1))
return ans;
}
}
class Solution(object):
def kSimilarity(self, A, B):
if A == B: return 0

N = len(A)
alphabet = 'abcdef'
pairs = [(a, b) for a in alphabet for b in alphabet if a != b]
index = {p: i for i, p in enumerate(pairs)}

count = [0] * len(index)
for a, b in itertools.izip(A, B):
if a != b:
count[index[a, b]] += 1

seen = set()
for size in xrange(2, len(alphabet) + 1):
for cand in itertools.permutations(alphabet, size):
i = cand.index(min(cand))

possibles = []
for cand in seen:
row = [0] * len(alphabet) * (len(alphabet) - 1)
for a, b in itertools.izip(cand, cand[1:] + cand[:1]):
row[index[a, b]] += 1
possibles.append(row)

ZERO = tuple([0] * len(row))
memo = {ZERO: 0}
def solve(count):
if count in memo: return memo[count]

ans = float('-inf')
for row in possibles:
count2 = list(count)
for i, x in enumerate(row):
if count2[i] >= x:
count2[i] -= x
else: break
else:
ans = max(ans, 1 + solve(tuple(count2)))

memo[count] = ans
return ans

return sum(count) - solve(tuple(count))

Intuition

Based on the underlying graph interpretation of the problem, we can prove that an optimal solution swaps the left-most unmatched character A[i] with an appropriate match A[j] == B[i] (j > i).

This reduces the number of “neighbors” of a node (string state) from  to , but it also focuses our search greatly. Each node searched with k matches, will have at most  swaps on the unmatched characters. This leads to  checked states. Furthermore, some characters are the same, so we must divide the number of states by approximate factors of  [where ​ is the number of occurrences of the ith character in A.] With , this means the number of states will be small.

Algorithm

We’ll perform a regular breadth-first search. The neighbors to each node string S are all the strings reachable with 1 swap, that match the first unmatched character in S.

Complexity Analysis

• Time Complexity: , where NN is the length of the string, and  is the length of the alphabet.
• Space Complexity: , where  is the time complexity given above.
class Solution {
public int kSimilarity(String A, String B) {
Queue<String> queue = new ArrayDeque();
queue.offer(A);

Map<String, Integer> dist = new HashMap();
dist.put(A, 0);

while (!queue.isEmpty()) {
String S = queue.poll();
if (S.equals(B)) return dist.get(S);
for (String T: neighbors(S, B)) {
if (!dist.containsKey(T)) {
dist.put(T, dist.get(S) + 1);
queue.offer(T);
}
}
}

throw null;
}

public List<String> neighbors(String S, String target) {
List<String> ans = new ArrayList();
int i = 0;
for (; i < S.length(); ++i) {
if (S.charAt(i) != target.charAt(i)) break;
}

char[] T = S.toCharArray();
for (int j = i+1; j < S.length(); ++j)
if (S.charAt(j) == target.charAt(i)) {
swap(T, i, j);
swap(T, i, j);
}

return ans;
}

public void swap(char[] T, int i, int j) {
char tmp = T[i];
T[i] = T[j];
T[j] = tmp;
}
}
class Solution(object):
def kSimilarity(self, A, B):
def neighbors(S):
for i, c in enumerate(S):
if c != B[i]:
break

T = list(S)
for j in xrange(i+1, len(S)):
if S[j] == B[i]:
T[i], T[j] = T[j], T[i]
yield "".join(T)
T[j], T[i] = T[i], T[j]

queue = collections.deque([A])
seen = {A: 0}
while queue:
S = queue.popleft()
if S == B: return seen[S]
for T in neighbors(S):
if T not in seen:
seen[T] = seen[S] + 1
queue.append(T)

## submitted solutions

class Solution:
def kSimilarity(self, A: str, B: str) -> int:

def dfs(a,b):
if not a:
return 0
one, two = [], []
for i in range(len(a)):
if a[0] == b[i]:
one.append(i)
if a[i] == b[0]:
two.append(i)
if two:                                     # one swap can delete two positions
i = two[0]
c, d = a[1:i]+a[i+1:], b[1:i]+b[i+1:]
return dfs(c,d) + 1
else:
res = float('inf')
for i in one:                           # one swap can only delete one position
c, d = a[i]+a[1:i]+a[i+1:], b[:i]+b[i+1:]
res = min(res, dfs(c,d)+1)
return res

a = ''
b = ''
for i in range(len(A)):
if A[i] != B[i]:                            # only consider unmatched positions
a += A[i]
b += B[i]
return dfs(a,b)
class Solution:
def kSimilarity(self, A: str, B: str) -> int:

def dfs(a,b):
if not a:
return 0
one, two = [], []
for i in range(len(a)):
if a[0] == b[i]:
one.append(i)
if a[i] == b[0]:
two.append(i)
if two:                                     # one swap can delete two positions
i = two[0]
c, d = a[1:i]+a[i+1:], b[1:i]+b[i+1:]
return dfs(c,d) + 1
else:
res = float('inf')
for i in one:                           # one swap can only delete one position
c, d = a[i]+a[1:i]+a[i+1:], b[:i]+b[i+1:]
res = min(res, dfs(c,d)+1)
return res

a = ''
b = ''
for i in range(len(A)):
if A[i] != B[i]:                            # only consider unmatched positions
a += A[i]
b += B[i]
return dfs(a,b)
class Solution:
def kSimilarity(self, A: str, B: str) -> int:

def dfs(a,b):
if not a:
return 0
one, two = [], []
for i in range(len(a)):
if a[0] == b[i]:
one.append(i)
if a[i] == b[0]:
two.append(i)
if two:                                     # one swap can delete two positions
i = two[0]
c, d = a[1:i]+a[i+1:], b[1:i]+b[i+1:]
return dfs(c,d) + 1
else:
res = float('inf')
for i in one:                           # one swap can only delete one position
c, d = a[i]+a[1:i]+a[i+1:], b[:i]+b[i+1:]
res = min(res, dfs(c,d)+1)
return res

a = ''
b = ''
for i in range(len(A)):
if A[i] != B[i]:                            # only consider unmatched positions
a += A[i]
b += B[i]
return dfs(a,b)
class Solution:
def kSimilarity(self, A: str, B: str) -> int:

def dfs(a,b):
if not a:
return 0
one, two = [], []
for i in range(len(a)):
if a[0] == b[i]:
one.append(i)
if a[i] == b[0]:
two.append(i)
if two:                                     # one swap can delete two positions
i = two[0]
c, d = a[1:i]+a[i+1:], b[1:i]+b[i+1:]
return dfs(c,d) + 1
else:
res = float('inf')
for i in one:                           # one swap can only delete one position
c, d = a[i]+a[1:i]+a[i+1:], b[:i]+b[i+1:]
res = min(res, dfs(c,d)+1)
return res

a = ''
b = ''
for i in range(len(A)):
if A[i] != B[i]:                            # only consider unmatched positions
a += A[i]
b += B[i]
return dfs(a,b)
class Solution:
def solve(self, s1:str, s2:str, mem:{(str,str):int}) -> int:
if len(s1)==0:return 0
if (s1,s2) in mem:return mem[(s1,s2)]
a,b,ans = s1[0],s2[0],float('inf')
for i in range(1,len(s1)):
if a==s2[i] and b==s1[i]:
mem[(s1,s2)] = self.solve(s1[1:i]+s1[i+1:],s2[1:i]+s2[i+1:],mem)+1
return mem[(s1,s2)]
for i in range(1,len(s1)):
if b==s1[i]:
ans = min(ans,self.solve(s1[1:i]+s1[0]+s1[i+1:],s2[1:],mem)+1)
mem[(s1,s2)] = ans
return mem[(s1,s2)]
def kSimilarity(self, A: str, B: str) -> int:
chars1,chars2 = [],[]
for i in range(len(A)):
if A[i]!=B[i]:
chars1.append(A[i])
chars2.append(B[i])
s1,s2 = "".join(chars1),"".join(chars2)
mem = {}
return self.solve(s1,s2,mem)
class Solution:
@lru_cache(None)
def kSimilarity(self, A: str, B: str) -> int:
if len(A) == 0: return 0                                                            #Base case

if A[0] == B[0]: return self.kSimilarity(A[1:],B[1:])                               #No cost

for i in range(1,len(B)):
if B[i] == A[0] and A[i] == B[0]:                                               #"clean" swap
return 1 + self.kSimilarity(A[1:i]+A[i+1:],B[1:i]+B[i+1:])

ans = math.inf
for i in range(1,len(B)):
if B[i] == A[0]: ans = min(ans, 1 + self.kSimilarity(A[1:],B[1:i]+B[0]+B[i+1:])) #Min cost
return ans
# cw Permutation graph + BFS

class Solution:
@lru_cache(None)
def kSimilarity(self, A: str, B: str) -> int:

if len(A) == 0: return 0

if A[0] == B[0]: return self.kSimilarity(A[1:],B[1:])

# Greedy optimization: prune matching pair from both strings
for i in range(1,len(B)):
if B[i] == A[0] and A[i] == B[0]:
return 1 + self.kSimilarity(A[1:i]+A[i+1:],B[1:i]+B[i+1:])

res = math.inf
for i in range(1,len(B)):
if B[i] == A[0]:
res = min(res, 1 + self.kSimilarity(A[1:],B[1:i]+B[0]+B[i+1:]))
return res
class Solution:
def kSimilarity(self, A: str, B: str) -> int:
if A == B:
return 0
if A[0] == B[0]:
return self.kSimilarity(A[1:],B[1:])

n = len(A)

matches = []
a, b = A[0], B[0]
for j in range(1, n):
if A[j] != B[j] and A[j] == b:
if a == B[j]:
return 1 + self.kSimilarity(A[1:j]+A[j+1:], B[1:j]+B[j+1:])
matches.append(j)

ans = n
for m in matches:
ans = min(ans, 1 + self.kSimilarity(A[1:m]+a+A[m+1:], B[1:]))
return ans
class Solution:
def kSimilarity(self, A: str, B: str) -> int:
if A == B:
return 0
if A[0] == B[0]:
return self.kSimilarity(A[1:],B[1:])

n = len(A)

matches = []
a, b = A[0], B[0]
for j in range(1, n):
if A[j] != B[j] and A[j] == b:
if a == B[j]:
return 1 + self.kSimilarity(A[1:j]+A[j+1:], B[1:j]+B[j+1:])
matches.append(j)

ans = n
B = B[1:]
for m in matches:
ans = min(ans, 1 + self.kSimilarity(A[1:m]+a+A[m+1:], B))
return ans
class Solution:
def kSimilarity(self, A: str, B: str) -> int:
if not A: return 0
if A[0] == B[0]: return self.kSimilarity(A[1:], B[1:])
for i in range(1, len(A)):
if A[0] == B[i] and B[0] == A[i]:
return 1 + self.kSimilarity(A[1:i]+A[i+1:], B[1:i]+B[i+1:])
res = 999999999
for i in range(1, len(A)):
if A[0] == B[i]:
res = min(res, 1 + self.kSimilarity(A[1:], B[1:i]+B[0]+B[i+1:]))
return res
class Solution:
def kSimilarity(self, A: str, B: str) -> int:

if B == A:
return 0

queue = deque()
visited = set()
queue.append((-1, B))
step = 0
n = len(A)
while queue:
level_size = len(queue)
for _ in range(level_size):
idx, curr = queue.popleft()

if curr == A:
return step

while idx < n and A[idx] == curr[idx]:
idx += 1

new_lst = list(curr)
for j in range(idx+1, n):
if new_lst[j] == A[idx] and A[j] != new_lst[j]:
new_lst[j], new_lst[idx] = new_lst[idx], new_lst[j]
new_str = ''.join(new_lst)
if new_str not in visited:
return step