Find the length of longest chain formed using given words in String

Question

Okk As programmer we love get involved in logic building but that is not the case some time we become blank over some type of puzzle as below mentioned. Let me declare that this is not any kind of homework or job stuff it simply a logic and performance practice puzzle.Okk the puzzle of given an Strings` with comma separated words like

String S= peas,sugar,rice,soup

Now crux is to find out length of longest chain of the words like last character of word should be the first character of next word and so on to create a longest possible chain and finally to calculate the length of that chain.

Now I had tried to figure out some sort of solution like

1. split the string with comma
2. add them in list
3. sort that list etc

but now how to develop further logic As I m little poor over logic development,Help is appreciated and if above half logic is not proper as it should be than what must the simple sort and perfect way to get the length of the longest chain of words.

Summary
input: String S= peas,sugar,rice,soup.
output: 4 length of words (peas->sugar->rice->soup) or (soup->peas->sugar->rice) etc

Answer 1

okk friends here the logic and core part which I had made and my puzzle got solved

import java.util.Map;
import java.util.Stack;

public class CandidateCode 
{ 
public static int chainLength=0;
public static void main(String[] args) {
    String s= "peas,sugar,rice,soup";
    int chainLengthfinal=wordChain(s);
    System.out.println("final length:"+chainLengthfinal);
}
public static int wordChain(String input1)
{
    List<String> stringList = new ArrayList<String>();
    stringList= Arrays.asList(input1.split(","));
    boolean ischain = new CandidateCode().hasChain(stringList);
    if (ischain) {
     return chainLength;    
    }
    return 0;

}
Map<Character, List<String>> startsWith = new HashMap<Character, List<String>>();
Map<Character, List<String>> endsWith = new HashMap<Character, List<String>>();

private Character getFirstChar(String str) {
    return str.charAt(0);
}

private Character getLastChar(String str) {
    return str.charAt(str.length() - 1);
}

boolean hasChain(List<String> stringList) {
    for (String str : stringList) {
        Character start = getFirstChar(str);
        Character end = getLastChar(str);
        List<String> startsWithList;
        List<String> endsWithList;

        if (startsWith.containsKey(start)) {
            startsWithList = startsWith.get(start);
        } else {
            startsWithList = new ArrayList<String>();
            startsWith.put(start, startsWithList);
        }

        if (endsWith.containsKey(end)) {
            endsWithList = endsWith.get(end);
        } else {
            endsWithList = new ArrayList<String>();
            endsWith.put(end, endsWithList);
        }
        startsWithList.add(str);
        endsWithList.add(str);
    }

    Stack<String> stringStack = new Stack<String>();
    for (String str : stringList) {
        if (hasChain(stringList.size(), str, stringStack)) {
            System.out.println(stringStack);
            System.out.println("size "+stringStack.size());
            chainLength= stringStack.size();
            return true;
        }
    }

    return false;
}

private boolean hasChain(int size, String startString, Stack<String> stringStack) {
    if (size == stringStack.size()) return true;
    Character last = getLastChar(startString);
    if (startsWith.containsKey(last)) {
        List<String> stringList = startsWith.get(last);
        for (int i = 0; i < stringList.size(); i++) {
            String candidate = stringList.remove(i--);
            stringStack.push(candidate);
            if (hasChain(size, candidate, stringStack)) {
                return true;
            }
            stringStack.pop();
            stringList.add(++i, candidate);
        }
    }

    return false;
 }
}

output of the above program will be
[soup, peas, sugar, rice]

size 4.

final length:4.