Auto comment: topic has been updated by sturdyplum (previous revision, new revision, compare).

This explanation may be a bit patchy, since it is purely from memory. I am sure EvgeniSergeev (who wrote this problem), or MathCrusader (who helped to develop it) can give a better explanation.

The idea is to build a graph containing 26 vertices (one for each letter), with the edges weighted by the number of transitions between those characters in the input string. We wish to count the number of optimal TSP-like tours. Doing this the typical way (Held-Karp recursions) will exceed the time limit. Instead, let's search for maximal disjoint path covers. (Since some edges have weight 0, let's ignore them, hence the 'disjoint' part of the path cover.) For clarity, we are looking for all ways of covering all vertices with disjoint paths such that no additional edge could be added--that is, they are maximal. All optimal permutations (of sewing machines) correspond to some permutation of the disjoint paths in a maximal cover. So, if we enumerate all of them, we can find the solution. How do we enumerate them all efficiently? Well, we can do a backtracking search with a heuristic. We will try adding some edges in each recursion, but not just any edges. Find the edge that, when picked, rules out the fewest number of edges. Call the set containing this edge, and the edges it rules out, S. Our backtracking search should try adding each element of S in turn, which causes all other edges in S to be ruled out. It turns out that if we always pick an edge that rules out the fewest number of edges (minimises |S|), we can do an analysis similar to enumerating all maximal independent sets, and get a complexity like O(3^|E| / 3|E|). Note that you will also need to deal with issues like accidentally creating loops during the backtracking search.