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

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.