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 P_1, P_2, \cdots⋯ be possible cycles of the underlying graph G. Let’s attempt to write G = \sum k_i P_i<em>​ for some constants k_i<em>​. Then, the number of cycles is \sum k_i.

We can represent G and P_i<em>​ as the number of directed edges from node X to Y. For example, if P_1​ is the cycle a -> b -> d -> e -> a, then P_1​ 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 G can also be represented as a column vector.

This sets the stage for dynamic programming. For each graph G, represented as a column vector, say we want to find numCycles(G). We can take all possible cycles C, and check if G contains C. 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: O(2^{N+W}), where N is the length of the string, and W is the length of the alphabet.
  • Space Complexity: O(2^{N+W}).
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;

                // Add count to possibles
                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]++;
                }
                possibles.add(row);
            }

        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) {
            ans.add(new String(""));
            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))
                    ans.add(alphabet[b] + rest);
        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))
                seen.add(cand[i:] + cand[:i])

        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 O(N^2) to O(N), but it also focuses our search greatly. Each node searched with k matches, will have at most 2^k swaps on the unmatched characters. This leads to \sum_k \binom{N}{k} 2^k = 3^N checked states. Furthermore, some characters are the same, so we must divide the number of states by approximate factors of \prod (N_i)! [where N_i<em>​ is the number of occurrences of the ith character in A.] With N \leq 20, 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: O(\sum_{k=0}^n \binom{N}{k} \frac{\min(2^k, (N-k)!)}{W * (\frac{N-k}{W})!}), where NN is the length of the string, and W is the length of the alphabet.
  • Space Complexity: O(N * t), where t 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);
                ans.add(new String(T));
                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))
        visited.add(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:
                            visited.add(new_str)
                            queue.append((idx, new_str))
                        new_lst[j], new_lst[idx] = new_lst[idx], new_lst[j]
            step += 1
        return step

Leave a reply