CODEWITHSUNDEEP
algorithmsortingsequence
iamnp
iamnp

Reputation: 510

Longest sequence of words with no repeating letters

I have a list of words. I need to choose the longest sequence of them with no repeating letters. For example, my words are:

ab
cd
cxyz

The longest sequence is (6 letters):

ab-cxyz

The order is not imoratant. I am looking for an efficient way of choosing such a sequence (list of 1000 words at least).

I tried to adapt the solution of Knapsack problem for this one but it gave the wrong result.

Upvotes: 1

Views: 222

Answers (1)

JuniorCompressor
JuniorCompressor

Reputation: 20015

You create a graph like this: for each word you create a node and you connect two words with an edge if they have a common letter. You also assign a weight to each node, which is word's length. You are now searching for an independent set of nodes, e.g a set of words with no edge between them. You also need this independent set to have a maximum weight.

This is an instance of maximum weight independent set problem and it's unfortunately a NP-hard problem without any known good approximation algorithms.

Upvotes: 1

Related Questions