Update: Following paragraph added
The bit mask isn't going to help by itself. It was just an idea for determining overlap. Because you require the matches on as fewest lines as possible, you have to try all possible combinations. This is why the problem is NP hard. I am assuming that for a given DNA sequence, the number of strands to place is quite large. If this assumption is correct, your perfect solution is going to be slow so you might want to look at a heuristic approach instead.

Thank you! I read about the "Bin packing problem", and some solutions to it. For what I need, an heuristic approach will be perfectly enough.

But first, I have to solve how to determine if the substring "fits in the can". The idea of "fitting" is that if there are whitespaces in the output line at the positions where each letter of my substring takes place, it "fits". I thought of spliting the string into an array, in a way that each letter is now an element of the array, and then to check if the elements of the array in the positions of my substring are whitespaces or not, but I am not sure if it is a good alternative.

rogerd,
Please see Re: Representing windows of time in a string for an example of using the bit string. Chances are, the solution from BrowserUk elsewhere in this thread is "good enough" solution.

Cheers - L~R