# Arranging $n$ double-sided cards to produce a given string

Suppose you're given a string $$s$$ that consists of lowercase alphabetic letters only. The length of the string is $$n$$. You are also given $$n$$ cards, which have lowercase alphabetic letters on the front and back. You want to arrange (shuffle and/or flip each card) the $$n$$ cards in an order that produces the string. You can use either side of a card, but obviously not both.

I am wondering if this problem can be converted to a Hungarian Algorithm problem? We essentially have a bipartite graph here. The left part consists of $$n$$ nodes representing each character in $$s$$. For each character in $$s$$, there is a subset of the $$n$$ cards that can can be used to create that character.

Can this be turned into a problem that can be solved with the Hungarian algorithm?

New contributor
roulette01 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Have you tried carrying out your idea? Where did you get stuck? – Yuval Filmus Jul 22 at 6:32
• I dont think this can be cast as a hungarian problem as there is no cost for each operation. Also the original problem I presume can be solved in about $O(n \log n)$ time via various sorting methods – Nikos M. Jul 22 at 8:20
• @YuvalFilmus The only idea I have that I know works for certain is to form an adjacency list for each s[i] and then do DFS with backtracking. But that algorithm is $O(n! * n)$, I believe. I am trying to see if the Hungarian algorithm works because that would reduce the complexity down to polynomial time. – roulette01 Jul 22 at 11:42
• @NikosM. Hm, I don't it's possible to solve this problem in sorting, let alone in O(n log n) time? You would sort the string s, I presume, but then, I don't think that makes the problem any easier? Each s[i] can still be formed with some subset of the given cards. – roulette01 Jul 22 at 11:44
• I was thinking of sorting both the cards (as joint pairs front-back) and the string, and then try a match – Nikos M. Jul 22 at 15:24