Longest string that can be made out of a list of strings

Question

I'm looking for an efficient algorithm which will give me the longest string which can be made out of a list of strings. More precisely:

Given a file containing large number of strings, find the longest string from the list of strings presented in the file, which is a concatenation of other one or more strings.

Note: The answer string should also belong to the list of strings in file.

Example input:

The
he
There
After
ThereAfter

Output:

ThereAfter

Answer 1

Sort list in descending length order for strings in the list (first in the list is longest string). Quicksort is sorting with average time complexity O(nlogn).

Then, iterate on strings in the list starting left.

From string S, iterate on elements s to its right. If s is a substring of S, remove s from S. Continue iterating to the right until S is empty, meaning that it is made of items of the list.

public static class ListCompare implements Comparator<String> {
    public int compare(String s1, String s2) {
        if (s1.length() < s2.length())
            return 1;
        else if (s1.length() > s2.length())
            return -1;
        else
            return 0;
    }
}

public static String longestSurString(String[] ss) {
    Arrays.sort(ss, new ListCompare ());
    for (String S: ss) {
        String b = new String(s);
        for (String s: ss) {
            if (!s.equals(b) && S.contains(s)) {
                S = S.replace(s, "");
            }
        }
        if (S.length() == 0)
            return b;
    }
    return null;
}