String Chain interview question was asked to me at the first step of hiring process. It was a bad experience as a whole, but i'm not a quitter. So i decided to write them here to force myself to understand deeply these kind of algorithm questions.

Copied the whole question below.

Question

Given an array, words, of n word strings (words[0], words[1],..., words[n-1]), choose a word from it and, in each step, remove a single letter from the chosen word if and only if doing so yields another word that is already in the library. Each successive character removal should be performed on the result of the previous removal, and you cannot remove a character if the resulting string is not an element in words(see Explanation below for detail). The length of a string chain is the maximum number of strings in a chain of successive character removals.

Complete the longestChain function in your editor. It has 1 parameter: an array of n strings, words, where the value of each element words; (where 0 <= i < n) is a word. It must return single integer denoting the length of the longest possible string chain in words.

Input Format

The locked stub code in your editor reads the following input from stdin and passes it to your function: The fist line contains an integer. n, the size of the words array. Each line i of the n subsequent lines (where 0 <= i < n) contains an integer describing the respective strings in words.

Constraints

1 <= n <= 50000

1 <= |words_i| <= 50, where 0 <= i < n

Each string in words is composed of lowercase ASCII letters.

Output Format

Your function must return a single integer denoting the length of the longest chain of character removals possible.

Sample Input 1
6  
a  
b  
ba  
bca  
bda  
bdca  
Sample Output 1
4  
Explanation

Sample Case 1: words = {"a", "b", "ba", "bca", "bda", "bdca"} Because "a" and "b" are single-character words, we cannot remove any characters from them as that would result in the empty string (which is not an element in words), so the length for both of these string chains is 1.

The word "ba" can create two different string chains of length 2 ("ba" -> "a" and "ba" -> "b"). This means our current longest string chain is 2.

The word "bca" can create two different string chains of length 3 ("bca" -> "ba" -> "a" and "bca" -> "ba" -> "b"). This means our current longest string chain is now 3.

The word "bda" can create two different string chains of length 3 ("bda" -> "ba" -> "a" and "bda" -> "ba" -> "b"). This means our current longest string chain is now 3.

The word "bdca" can create four different string chains of length 4 ("bdca" -> "bda" -> "ba" -> "a" , "bdca" -> "bda" -> "ba" -> "b", "bdca" -> "bca" -> "ba" -> "a", "bdca" -> "bca" -> "ba" -> "b"). This means our current longest string chain is now 4.

Given Empty Method
static int longestChain(String words[]) {  
...       
}

My Solution
import java.util.*;

/**
 * Created by cancobanoglu on 11/09/16.
 */
public class StringChain {

    public static void main(String[] args) {
        String[] words = {"a", "b", "ba", "bca", "bda", "bdca"};
        int longestChain = longestChain(words);
        System.out.println("longestChain " + longestChain);
    }

   static int longestChain(String words[]) {
        List<String> wordList = Arrays.asList(words);
        int max = Integer.MIN_VALUE;
        for (String word : words) {
            int current = processWord(word, wordList);
            if (max < current) {
                max = current;
            }
            System.out.println(current);
        }

        return max;
    }

    static int processWord(String word, List<String> allWords) {
        if (word.length() == 1)
            return 1;

        Stack<String> wordsStack = new Stack<String>();
        wordsStack.add(word);

        // start and end indices which hold character is dropped from the current word
        int startIndex = 0;
        int endIndex = 1;

        while (!wordsStack.isEmpty()) {
            String currentWord = wordsStack.peek();

            if (endIndex > currentWord.length()) {
                break;
            }

            if (allWords.contains(currentWord)) {
                StringBuilder wordBuilder = new StringBuilder(currentWord);
                wordBuilder.delete(startIndex, endIndex);
                wordsStack.add(wordBuilder.toString());
            } else {
                wordsStack.pop();
                startIndex++;
                endIndex++;
            }
        }

        return wordsStack.size();
    }
}