C: Find the string which is made up of maximum number of other strings ?

Question

"Given an array of strings, find the string which is made up of maximum number of other strings contained in the same array. e.g. “rat”, ”cat”, “abc”, “xyz”, “abcxyz”, “ratcatabc”, “xyzcatratabc” Answer: “xyzcatratabc”

Answer 1

I would prefer LCS with dynamic programming.

for more ideas check following link
http://www.careercup.com/question?id=5647413305933824

Answer 2

Following will not just print the best rather print all in the order -

public static void main(String[] args) {
        ArrayList<String>list = new ArrayList<>();
        list.add( "rat");
        list.add( "cat");
        list.add( "abcxyz");        
        list.add( "abc");
        list.add( "xyz");
        list.add( "ratcatabc");
        list.add( "xyzcatratabc" );

        Map<String, Integer> map = new HashMap<String, Integer>();

        for(int i=0; i<list.size()-1; i++){
            String s = list.get(i);         
            for(int j=0; j < list.size(); j++){
                if(i==j){
                    continue;
                }
                if(list.get(j).contains(s)){
                    Integer v = map.get(list.get(j));
                    if(v == null){
                        map.put(list.get(j), 0);
                    }else{
                        map.put(list.get(j), v+1);
                    }
                }

            }   

        }
        System.out.println(map);        
    }