remove fragments in a sentence [puzzle]

First observation: replace each word with a single "letter" in a big alphabet(i.e. hash the worlds in some way), remove whitespaces and punctuation.

Now you have the problem reduced to remove the longest letter sequence that appears in all words of a given list. So you have to compute the longest common substring for a set of "words". You find it using a generalized suffix tree as this is the most efficient algorithm. This should do the trick and I believe has the best possible complexity.