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 , where are the lengths of the cycles in some cycle decomposition of the underlying graph. This can be re-written as . 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, ie. by always removing the lowest size cycle. For example, consider the graph with edges a -> b -> c -> a, b -> 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: .


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 th 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 is the length of the string, and is the length of the alphabet.

  • Space Complexity: , where is the time complexity given above.


Analysis written by: @awice.