Check if given string can be created by a set of characters cut out from magazine article

Question

"Observe that when you cut a character out of a magazine, the character on the reverse side of the page is also removed. Give an algorithm to determine whether you can generate a given string by pasting cutouts from a given magazine. Assume that you are given a function that will identify the character and its position on the reverse side of the page for any given character position."

How can I do it?

I can do some initial pruning so that if a needed character has only one way of getting picked up, its taken initially before turning the sub-problem for dynamic technique, but what after this initial pruning?

What is the time and space complexity?

Answer 1

As @LiKao suggested, this can be solved using max flow. To construct the network we make two "layers" of vertices: one with all the distinct characters in the input string and one with each position on the page. Make an edge with capacity 1 from a character to a position if that position has that character on one side. Make edges of capacity 1 from each position to the sink, and make edges from the source to each character with capacity equal to the multiplicity of that character in the input string.

For example, let's say we're searching for the word "FOO" on a page with four positions:

pos    1 2 3 4 front  F C O Z back   O O K Z 

We then generate the following network, ignoring position 4 since it does not provide any of the required characters.

Now, we only need to determine if there is a flow from the source to the sink of length("FOO") = 3 or more.