Minimum number of swaps required to make a given anagram to another anagram [closed]

Question

Given two anagrams S1 and S2, we want to convert S1 anagram to S2 anagram. We need to find out minimum number of adjacency swaps required for this.

For Example: S1:CAT and S2:ACT. Here minimum number of swaps is only 1. swap C to A to get S2.

How can we do it using Dynamic programming. Is it possible?

Answer 1

One approach to obtain optimal solution is reducing the problem to a shortest path problem.

In here, each vertex is one possible anagram using the given letters. An edge between two vertices (anagrams) exists if and only if you can move from the one to the other with a single swap.

Finding the shortest path from the input anagram to the desired one will give you the optimal number of paths.

Shortest path problem for unweighted graphs can be solved with BFS, bi-directional BFS or A* algorithm.